A school must schedule n exams (numbered 0 to n - 1). Two exams clash if some student
takes both, and clashing exams cannot be in the same time slot. clashes lists the clashing pairs
(a, b). Write schedule_exams(n, clashes) that returns a list slot of length n, where
slot[i] is the slot (a whole number, 0 or more) of exam i, using as few different slots as
you can.
The tests build their lists with exam_clashes(n, density, seed): each pair of exams clashes with
probability density. It is available in your code, so you can try it with Run.
How this problem is scored
A timetable passes if no clashing pair shares a slot and it uses no more slots than this simple rule: take the exams in index order and give each the lowest slot that no clashing exam already has. Its quality (0 to 100) says how much of the gap between that rule and the best timetable we know you close: 0 matches the rule, 100 matches (or beats) the best known one. The best known values come from long searches; nobody has proved they are optimal.
Examples
Input: n = 6, clashes = [(0, 3), (0, 5), (1, 2), (1, 4), (2, 5), (3, 4)]
Output: [0, 1, 0, 1, 0, 1]
Explanation: exams 0, 2 and 4 never clash with each other, nor do 1, 3 and 5,
so two slots are enough. Index order uses three:
0 -> 0, 1 -> 0, 2 -> 1, 3 -> 1, 4 -> 2, 5 -> 2.
Input: n = 60, clashes = exam_clashes(60, 0.5, 1)
Output: any valid timetable with no more slots than the index-order rule
Constraints
1 <= n <= 200,0 <= density <= 0.5- Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.
Goals
- See how much the order of a greedy construction matters
- Pick the next element by how constrained it is
- Improve a solution by rebuilding it in orders that can never make it worse