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.
tapananand
13
Junior Poster
Recommended Answers
Jump to PostSince 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.
Jump to PostYou're finding the set of all subsets such that the subsets do not contain overlapping intervals, correct? I thought you implied from your description that you're backtracking.
Jump to PostCan you be more clear what the problem is?
It doesn't sound like that will solve the problem of sinding the set of all subsets such that the subsets do not contain overlapping intervals.
All 11 Replies
Hiroshe
499
Posting Whiz in Training
tapananand
13
Junior Poster
Hiroshe
499
Posting Whiz in Training
tapananand
13
Junior Poster
Hiroshe
499
Posting Whiz in Training
tapananand
13
Junior Poster
Hiroshe
499
Posting Whiz in Training
tapananand
13
Junior Poster
Hiroshe
499
Posting Whiz in Training
tapananand
13
Junior Poster
tapananand
13
Junior Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.