Suppose you have a list of S students, a list of C classes and a list of which modules each student takes. I want to schedule every class during a 5 day exam period.
Constraints: Their are only 2 exam slots per day. If there is a pair of modules where one or more students are taking both modules, we cannot schedule their exams at the same time.
My attempt: To show something is NP Complete, must show it is in NP and a reduction of an NP Hard Problem. Clearly, it is in NP because given a certificate of a scheduling, you can just check there are no conflicts.
I want to show this is a reduction of either SAT or Graph Coloring. I'm not sure exactly how to go about that.