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