Algorithms Lecture 17: Greedy Algorithms, Room Scheduling Problem (Interval Graph Coloring)

[@blingket]

Thank you so much, it was exactly what I needed

[@Faad3e]

grande fran suscrito altok

[@fabiancid2053]

grande Leopoldo suscrito altok

[@RedEnergySounds]

Sir, thank you for the great lecture, pretty straightforward and simple to understand. But may I ask one question? What happens if an activity is bound to a resource? For example what happens if a3 should be on r1 and we can't change it? Won't a1 overlap? Thank you

[@赖清德-w8f]

thank you for your lecture, very clear. in the code, you need to sort events by time ascending order and event type alphabetically ascending order, right? otherwise it's likely s2 is before f1 in the list because they have same time. another question is in the code, we need a different way to capture which activity is assigned which room I think, otherwise, if it's a start event, we assign Event[i].activity.room = room, but when we process finish event for the same activity, Event[i].activity.room is empty, because the room is set in activity's start event.

[@abhishekchaudhary6975]

Thank you!!

[@Maxwellpaulwall]

There is nothing in the sort algorithm that guarantees if S1, S2, S3, ... Sn and F1, F2, F3, ... Fm are equal, that they will appear in alternating order. This means the algorithm encounter all the start times with time = x, before all the finish times with time = x. The algorithm will assign new rooms before realizing an event ended in a room that was already used. To fix this I would suggest modifying the sort algorithm to make sure the Fi comes first if its equal to an Si, or perhaps change the datastructure and way of checking it.

[@ghassanshobakicomputerscie9478]

Yes, you are absolutely right. Thank you for catching this subtlety! Making sure that finish times appear before start times in the sort is an implementation detail that we don't necessarily mention in the pseudo-code. Of course, mentioning this in the pseudo-code would make it more precise. However, pseudo-code will never be as precise as real code that is written in a specific programming language.

[@inkuumba]

@@ghassanshobakicomputerscie9478 This ordering was mention in the video at minute around 13.18. It wasn't an oversight. Thanks Prof. for your videos

[@asdfasdfuhf]

What chaptor in CLRS touches upon the room sceduling problem (interval graph coloring) ?

[@ghassanshobakicomputerscie9478]

Good question! It is not covered in any section, but it is introduced in the Third Edition as Problem 16.1-4 on Page 422. I cover it, because I think it is an excellent example of a problem that is NP-complete in its general form (Graph Coloring) but has a special case (Interval Graph Coloring) that can be solved using an extremely simple and intuitive nlogn greedy algorithm, and this special case happened to have many interesting applications in practice.