CareerCup

I don't know if I'm missing something, but the solution seems very simple to me. Please let me know if I'm wrong.
Here I have skipped the sorting and categorizing steps.
Both birth years and death years are sorted together into a single array with a flag to indicate whether each entry is a death year or a birth year. I simply scan through the array incrementing the count on encountering a birth and decrementing the count on encountering a death. I also keep track of the maximum value of the count at any point in time.

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

enum EventType {
	BIRTH, DEATH
};

struct Event {
	int year;
	enum EventType eventType;
};

int main() {
	//Input will not be given in sorted fashion. Here it is sorted for convenience.
	//Normally quicksort can be used to sort before proceeding with the algorithm
	struct Event events[] = {{-80000, BIRTH}, {79950, DEATH}, {20 , BIRTH}, {22, BIRTH}, {58, BIRTH}, {60, DEATH}, {65, DEATH}, {70, DEATH}, {1950, BIRTH}, {2004, DEATH}};
	int i;
	int eventCount = 5;
	int aliveDinoCount = 0;
	int maxAliveDinoCount = 0;
	for (i = 0; i < (eventCount * 2); i++) {
		struct Event event = events[i];
		if (event.eventType == BIRTH) {
			aliveDinoCount++;
		} else {
			aliveDinoCount--;
		}
		if (aliveDinoCount > maxAliveDinoCount)
			maxAliveDinoCount = aliveDinoCount;
	}
	printf("Maximum alive dinosaurs: %d\n", maxAliveDinoCount);
	return 0;
}

Wrote this in C. Haven't implemented sorting of basin sizes.

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


struct Cell {
	int elevation;
	int basinIndex;

};

struct Cell *elevationData[5000][5000];
int plotSize;
int currentBasinIndex;
int *basinSizes;

struct Cell* new_Cell() {
	struct Cell* cell = (struct Cell*) malloc(sizeof(struct Cell));
	cell->elevation = 0;
	cell->basinIndex = -1;
	return cell;
}

void processCell(int i, int j) {
	int minElevation = 500;
	struct Cell *cell = elevationData[i][j];
	struct Cell *left = NULL, *top = NULL, *right = NULL, *bottom = NULL;
	int minElevationCellI, minElevationCellJ;
	if (cell->basinIndex != -1)
		return;
	if ((i - 1) >= 0) {
		left = elevationData[i - 1][j];
		if (left->elevation < minElevation) {
			minElevation = left->elevation;
			minElevationCellI = i - 1;
			minElevationCellJ = j;
		}
	}
	if ((i + 1) < plotSize) {
		right = elevationData[i + 1][j];
		if (right->elevation < minElevation) {
			minElevation = right->elevation;
			minElevationCellI = i + 1;
			minElevationCellJ = j;
		}
	}
	if ((j - 1) >= 0) {
		top = elevationData[i][j - 1];
		if (top->elevation < minElevation) {
			minElevation = top->elevation;
			minElevationCellI = i;
			minElevationCellJ = j - 1;
		}
	}
	if ((j + 1) < plotSize) {
		bottom = elevationData[i][j + 1];
		if (bottom->elevation < minElevation) {
			minElevation = bottom->elevation;
			minElevationCellI = i;
			minElevationCellJ = j + 1;
		}
	}
	if (minElevation > cell->elevation) {
		//Current cell is the sink. Form a new basin
		cell->basinIndex = ++currentBasinIndex;
	} else {
		processCell(minElevationCellI, minElevationCellJ);
		cell->basinIndex = elevationData[minElevationCellI][minElevationCellJ]->basinIndex;
	}
	basinSizes[cell->basinIndex]++;
}

int main() {
	int i, j, dummy;
	currentBasinIndex = -1;
	scanf("%d", &plotSize);
	basinSizes = (int *) calloc(plotSize * plotSize, sizeof(int));
	for (i = 0; i < plotSize; i++) {
		for (j = 0; j < plotSize; j++) {
			elevationData[i][j] = new_Cell();
			scanf("%d", &(elevationData[i][j]->elevation));

		}
	}
	for (i = 0; i < plotSize; i++) {
		for (j = 0; j < plotSize; j++) {
			processCell(i, j);
		}
	}

	for (i = 0; i <= currentBasinIndex; i++) {
		printf("%d ", basinSizes[i]);
	}
	scanf("%d", &dummy);
	return 0;
}