Interval Scheduling Greedy Algorithm

The concept behind Interval Scheduling Greedy Algorithm is that we have a set of jobs (tasks) that need to be scheduled on a machine, and each job j has a start time Sj and a finish time Fj. We can’t schedule two jobs at the same time if they overlap. Our objective is to fill our machine with as many jobs as possible. Wikipedia definition of Interval-Scheduling-Greedy-Algorithm HERE.

Example

Consider the following five work intervals: [1, 3], [2, 4], [3, 5], [4, 6], [5, 7]. Then, the three jobs [1, 3], [3, 5], and [5, 7] should be scheduled. Any other option will only schedule two jobs.
Let’s have a look at a few greedy algorithms that don’t work. Let’s see if we can come up with some counter-examples for each one. “candidate job” doesn’t clash with any other planned work.

Algorithm

An effective algorithm that works is:

• Always add in the candidate job with the earliest completion time, starting with an empty schedule if at least one candidate job exists.

Sort all activities by their finishing time.

Initially A = {}
For j = 1 to n {
         if (activity j is compatible with A)
                add j to A
         EndIf
EndFor 
Return A

Proof

Base Case: All activites are Compatible, when A is the empty set.

Hypothesis: All activities i < j in A are compatible.

Induction Step:

  • If j is not an element of A, then all activities i <= j in A are compatible.
  • if j is element of A, add element j to A and check for is j compatible with A?

In both cases, all activities i <= j are compatible.


Posted

in

by