Any Counter Example for my Algorithm - Task Scheduling

[tapananand]

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.

[Hiroshe]

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.

[tapananand]

What do you mean by:

you're still backtracking through all of the possiblities

[Hiroshe]

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.

[tapananand]

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.

[Hiroshe]

Can 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.

[tapananand]

We've to find the minimum sized set of subsets and not all of them

[Hiroshe]

Are you saying that each element may only exist in one subset?

[tapananand]

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.

[Hiroshe]

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.

A trivial counter example would be:

{(0, 5), (5, 10), (4, 9), (10, 11)}

Where your algorithm would produce:

{[(10, 11), (5, 10)],
 [(4, 9)],
 [(0, 5)]}

But the most optimal solution is:

{[(0, 5), (5, 10)],
 [(4, 9), (10, 11)]}

From my vauge understanding of your description.

[tapananand]

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:

1. [(0, 5), (5, 10), (10, 11)].
2. [(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.

[tapananand]

Here is a counter example I got:

{(1, 2), (2, 5), (1, 3), (3, 4)}

My Algo gives:

1. [(1, 2), (3, 4)]
2. [(1, 3)]
3. [(2, 5)]

while optimum is:

1. [(1, 2), (2, 5)]
2. [(1, 3), (3, 4)]