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 RepliesReply to this topic
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.