So we cannot find this with choosing earliest finish time, the time did not tell you anything. Try to think like this: For all time, there are MAXIMUM 5 exams happening at the same time, you have AT LEAST to use 5 classrooms (colors), right? You are forced to pick ALL intervals, while the answer of the problem is THE MAXIMUM # of CONFLICTED INTERVALS OF ALL TIME. Start time earlier than A's finish time, there is conflict, I can only choose A OR B, however, A ends earlier, it gives a higher chance to pick more shows afterwards, no?įor coloring problem, however, it is totally another category of problem.Start time later than A's finish time, then no conflict at all, why not both?.If there is two intervals A, B, with A has earlier finish time, then B is either I CANNOT get better result if I'm NOT choosing the show having the earliest finish time, let's see. I am trying to give reasons to make it more intuitive.įirst, for scheduling problem, you can indeed prove greedy algorithm works. If you only need a counter example of greedy algorithm on coloring, provides one already.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |