I guess most of you would have seen the algorithm for the following problem: Input: Set of intervals(time) Output: Partion of intervals into minimum subsets such that no interval in a subset overlaps. The Algorithm: Sort intervals by start times and look them in this order, put each interval in the first subset in which it can(without overlap). My Question: Is the following approach wrong?? My Approach: Sort intervals by ending times, put each interval in the first subset in which it can(without overlap).
Please help. This approach is not given anywhere. I guess a counter example will do, but I can't really find any.
No i'm not backtracking at all.
This is what I am doing(going closer to implementation):
Sort intervals by ending times.
The first one say I1 goes to set1. In an array store end times for each subset.
so arr = I1.end.
Now, see the next interval in the sorted list.
if I2.start > arr, then I2 goes into set 1, else we need a new set, s.t
arr = I2.end and set 2 has I2.
Now for I3, if I3.start > arr put in set1 , else if I3.start > arr put in set 2 else new set3.
At any point when I put an Interval in a set arr[set] is update to the end time of last interval put into it.
Yes. You can think of it as some users asking to get their tasks done on computers between fixed time intervals they give and you have to schedule them on minimum number of computers - tasks are non-preemptive and only one task at a time can execute on a computer.