ECE NTUA Computer Languages (Γλώσσες Προγραμματισμού) skitrip Greedy Algorithm.

skitrip.c

#include <stdlib.h>
#include <stdio.h>

//Structure to save Height and Position of each station
struct station_struct {
	long height;
	long position;
};

//Quicksort comparator
int tzompare(const void *a, const void *b) {
	struct station_struct *pa = (struct station_struct *) a;
	struct station_struct *pb = (struct station_struct *) b;
	if (pa->height == pb->height)
		//Height[a] == Height[b] so a < b if Position[a] < Position[b] else a > b
		return (pa->position - pb->position);
	else
		//a < b if Height[a] < Height[b] else a > b
		return (pa->height - pb->height);
}

int main(int argc, char **argv) {
	//check if given input file
	if (argc < 2) {
		printf("Usage ./skitrip <in>\n");
		exit(1);
	}
	//open input file as readonly (fails otherwise)
	FILE *fp;
	fp = fopen(argv[1], "r");
	if (fp == NULL) {
		printf("Null pointer did not open file successfully\n");
		exit(1);
	}
	//read first number => number of stations
	long nstations;
	if (fscanf(fp, "%ld\n", &nstations) < 1) {
		printf("Not a number\n");
		fclose(fp);
		exit(1);
	}
	//create a pointer of type station_struct and allocate memory
	struct station_struct *stations;
	stations = malloc(sizeof(struct station_struct) * nstations);
	//read each following number and store the height and the position of each station
	for (long i = 0; i < nstations; i++) {
		if (fscanf(fp, "%ld\n", &stations[i].height) < 1) {
			printf("Not a number\n");
			fclose(fp);
			exit(1);
		}
		stations[i].position = i + 1;
	}
	fclose(fp);
	//sort stations array ascending with Quicksort O(nlogn)
	qsort(stations, nstations, sizeof(struct station_struct), tzompare);
	long endpoint, d;
	//endpoint of skitrip is the lowest station initially
	endpoint = stations[0].position;
	//distance of skitrip is 0 if Katerina descends at the lowest station
	d = 0;
	//traverse the array starting from the lowest station to the heightest
	for (long i = 0; i < nstations; i++) {
		//endpoint can be placed further back
		if (endpoint > stations[i].position)
			endpoint = stations[i].position;
		//greedy approach to maximise the distance
		if (d < stations[i].position - endpoint)
			d = stations[i].position - endpoint;
	}
	//print out the distance
	fprintf(stdout, "%ld", d);
	return 0;
}