CODEWITHSUNDEEP
algorithmjob-schedulinggreedy
Muaaz Khalid
Muaaz Khalid

Reputation: 2249

Counter example for Job Scheduling Algorithm "Earliest End time First"

Well, we have the greedy algorithm for the job scheduling (scheduling the maximum number of jobs). we can use different techniques

  1. Shortest job first
  2. Earliest start time first
  3. Job with minimal conflicts first
  4. Earliest end time first

I have the counter example of first three strategies but I couldn't find the counter example for the fourth one.

here are the counter examples for first three methods

Shortest Job First :

Here we can schedule 2 jobs instead of one shorter. enter image description here

Earliest start time first :

Here we can schedule 6 smaller job that starts later instead on one that start earlier enter image description here

Job with minimal conflicts first :

Here we can schedule 4 jobs with conflicts 3,4,4,3 instead of 3 with minimal conflicts, that's 2,3,3

enter image description here

So, what would be the counter example of the last one Earliest end time first I couldn't find the counter example for this. So, it always gives an optimum solution for each set of data?

UPDATE 1 :

I have one executor to execute the job and I want to execute the maximum number of jobs.

Upvotes: 3

Views: 3009

Answers (1)

Rishit Sanmukhani
Rishit Sanmukhani

Reputation: 2269

Earliest End time First is the greedy algorithm which gives optimal algorithm for above mentioned problem. (Actually the problem you have mentioned is called Interval Scheduling problem)

The proof can be done using charging argument. You compare the output of greedy algorithm to optimal solution and argue that you solution is not worse than optimal.

Upvotes: 6

Related Questions