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 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.