# Task Scheduling Algorithm - Counter Example

Page 1 of 1

## 3 Replies - 1995 Views - Last Post: 24 June 2014 - 06:41 AM

### #1 tapananand

Reputation: 0
• Posts: 3
• Joined: 14-May 12

# Task Scheduling Algorithm - Counter Example

Posted 24 June 2014 - 04:40 AM

I guess most of you would know the algorithm for the following problem:

Input: Set of intervals(time)
Output: Partition of intervals into minimum subsets such that no interval in a subset overlaps.

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.

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

For Example:
Let the intervals be: {(0, 5), (5, 10), (4, 9), (10, 11)}
Then output should be:
[(0, 5), (5, 10), (10, 11)].
[(4, 9)].
Which uses minimum i.e 2 subsets or 2 computers.
Please help. This approach is not given anywhere so is it wrong? I guess a counter example will do, but I can't really find any. All cases that I've considered give correct results.

Is This A Good Question/Topic? 0

## Replies To: Task Scheduling Algorithm - Counter Example

### #2 sepp2k

• D.I.C Lover

Reputation: 2754
• Posts: 4,411
• Joined: 21-June 11

## Re: Task Scheduling Algorithm - Counter Example

Posted 24 June 2014 - 05:50 AM

How about {(1, 2), (1, 3), (3, 4), (2, 5)}?

### #3 tapananand

Reputation: 0
• Posts: 3
• Joined: 14-May 12

## Re: Task Scheduling Algorithm - Counter Example

Posted 24 June 2014 - 06:14 AM

sepp2k, on 24 June 2014 - 05:50 AM, said:

How about {(1, 2), (1, 3), (3, 4), (2, 5)}?

Thanks, my algo gives 3 while optimum is 2.

• Saucy!

Reputation: 6258
• Posts: 24,026
• Joined: 23-August 08

## Re: Task Scheduling Algorithm - Counter Example

Posted 24 June 2014 - 06:41 AM

No C/C++ here, moved to Computer Science.