# Find an assignment of courses to days so that no student has more than one exam on the same day is NP-complete?

Given a list of $N$ courses, $M$ students, the list of courses each student is taking and an integer $K$ representing the duration of the exam phase, is there an exam schedule consisting of $K$ dates so that there are no conflicts? Can you show that this problem is as difficult as the Clique-Cover problem (is $NP$-complete)?

• If $K>N$ the problem is easy. – Henrik supports the community Dec 27 '14 at 17:31
• Hint: Consider the graph with a vertex for each course and an edge between two courses if they have a student in common. Is it $K$-colorable? (If you want to reduce from clique cover instead, put edges between courses with disjoint sets of students). – hmakholm left over Monica Dec 27 '14 at 18:35

Let the courses be vertices. Draw an edge between two if those courses have no student in common, i.e. their exams may be scheduled concurrently. If there happens to be a $3$-clique, then all $3$ of those courses may have their exams at the same time.