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.
Jump to Post
Since you're still backtracking through all of the possiblities (no assumptions have been made), it will work fine.
It might be also interesting to note that this problem is an exact cover problem.
All 11 Replies
We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.