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

#1 tapananand   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2754
  • View blog
  • 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)}?
Was This Post Helpful? 3
  • +
  • -

#3 tapananand   User is offline

  • New D.I.C Head

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

Re: Task Scheduling Algorithm - Counter Example

Posted 24 June 2014 - 06:14 AM

View Postsepp2k, 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.
Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades   User is offline

  • Saucy!
  • member icon

Reputation: 6258
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1