0
$\begingroup$

In CLRS, an approach has been given to prove the optimal substructure and the correctness of the greedy algorithm for the activity selection problem. In the Lecture Hall assignment problem, we sort the classes according to their starting times and assign them lecture halls accordingly, choosing a new lecture hall if the timings of the class conflict with all the existing lecture halls. Is there a way to prove the optimal substructure in this problem? Why do we only sort the lectures according to their starting times and not according to their finishing times? How can we prove that there is always an optimal solution which makes the greedy choice?

$\endgroup$
  • 1
    $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W. Mar 29 at 18:24
  • $\begingroup$ @D.W. I am still not able to understand why we need to sort the classes on the basis of their starting times and not their finishing times. $\endgroup$ – Pratham Yadav Mar 30 at 6:49
  • $\begingroup$ The best way to understand that is to try to prove it correct, or look for a counterexample, both ways, and see what happens. $\endgroup$ – D.W. Mar 30 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.