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.

You'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.

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[0] = I1.end.
Now, see the next interval in the sorted list.
if I2.start > arr[0], then I2 goes into set 1, else we need a new set, s.t
arr[1] = I2.end and set 2 has I2.
Now for I3, if I3.start > arr[0] put in set1 , else if I3.start > arr[1] 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.

It sounds like you're implmenting a greedy algortihm to get a heuristic (ie, you're generating one solution as oppposed to testing all combinations).

If you wanted to get an exact accurate answer, you would need to examine all of the possibilities (backtracking). This can be optimized with branch and bounding.

Sorry, I didn't consider the case of equal end time of one interval and start time of other. So my check should be I[j].start >= arr[i]and then my algo gives:

[(0, 5), (5, 10), (10, 11)].

[(4, 9)].
Which uses minimum i.e 2 computers or subsets.

By the way optimizing here just refers to minimizing the number of subsets of intervals formed and not that each subset is of equal or almost equal size.

Dear Friends,
I developed Desktop application in C# .Net for client. client purchased software and installed it one than more system without my permission. How to restict him to not ...