Interval Scheduling

Greedy Algorithm to find the maximum number of mutually compatible jobs

Problem Statement

• Job j starts at s(j) and finishes at f(j)
• 2 jobs are compatible if they do not overlap (2nd job starts after or at the same time as the 1st one finishes)
• Goal: find the maximum number of mutually compatible jobs
• Example: 8 jobs {a, b, c, d, e, f, g, h}

Optimal = {b, e, h}

Algorithm

Consider jobs in ascending order of finish time f(j)

Sorted Jobs

Pseudocode

Runtime

Sorting O(n log(n)) + for-loop Θ(n)
O(n log(n))

References

• Kevin Wayne Slides
• University of Washington Slides
• T. M. Murali Slides
• Carl Kingsford Slides
• Violetta lonati Slides