[P and NP] In a university, several classes are conducted on the same day. Each class is given a time interval [tbegin, tend] which indicates the starting and ending times of the class. Suppose that you are given n-classes C = {c1, c2, . . . , cn} with the meeting times, the CLASSROOM problem is to decide whether k classrooms are sufficient to run all the classes. Formally,
CLASSROOM = { | classes C can be scheduled with k classrooms }
1) Show that CLASSROOM is in NP. That is, given an instance ? CLASSROOM, what is the certificate and verifier algorithm for . Writing a pseudo-code for the verifier algorithm suffices.
2) What is the size of the certificate in terms of the input size? What is the time complexity of the verifier? You need not prove your answer, providing explanation for the time complexity suffices.
Hint: Consider an instance of CLASSROOM as a dependency graph and apply known graph algorithms.