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

struct SCourse {                                         	/* Struktura udržující informace o jedné přednášce. */ 
	int idx;	// index přednášky
	int start;	// čas začátku
	int finish;	// čas konce
};

int loadCourses(struct SCourse **courses) {              	/* Funkce načítající přednášky ze souboru do pole courses. */ 
	int count;
	FILE *fp = fopen("prednasky.in", "r");
	fscanf(fp, "%d\n", &count);
	*courses = (struct SCourse*)malloc(count * sizeof(struct SCourse));
	
	for(int i = 0; i < count; i++) {
		fscanf(fp, "%d %d\n", &((*courses)[i].start), &((*courses)[i].finish));
		(*courses)[i].idx = i+1;
	}
	fclose(fp);
	return count;
}

int courseCompare(const void *course1, const void *course2) {  	/* Funkce porovnávající přednášky dle času konce. */ 
	return ((struct SCourse*)course1)->finish - ((struct SCourse*)course2)->finish;
}

/* Implementace hladového algoritmu nad přednáškami. Vybrané přednášky rovnou ukládá do výstupního souboru. */ 
void greedy(struct SCourse *courses, int count) {
	if (count < 1) return;
	
	int i = 0, resCount = 0, last = -1;
	while(i < count) {
		if (i != resCount) courses[resCount] = courses[i];
		last = courses[resCount].finish;
		resCount++;  i++;
		while((i < count) && (courses[i].start <= last)) i++;   // hladově vybereme další přednášku
	}

	FILE *fp = fopen("rozvrh.out", "w");				// výpis nalezených přednášek do souboru
	fprintf(fp, "%d\n", resCount);
	for(i = 0; i < resCount; i++) fprintf(fp, "%d ", courses[i].idx);
	fclose(fp);
}

int main() {
	struct SCourse *courses;
	int count;
	
	count = loadCourses(&courses);
	qsort(courses, count, sizeof(struct SCourse), courseCompare);
	greedy(courses, count);
	return 0;
}