Interval Scheduling

Unweighted Algorithm

Problem: Job $j$ starts at $s_{j}$ and finishes at $f_{j}$ . Goal is to find maximum set of jobs that do not overlap.

Algorithm: Sorts jobs by finish time (ascending) and then go through the list, taking compatible jobs (Greedy Algorithms)

Time complexity: $O (n lo g n)$ due to that sorting step at the start

Theorem

The earliest-finish-time-first algorithm is optimal

Proof:

Assume by way of contradiction, that the greedy algorithm is not optimal.
Let $i_{1}, i_{2}, \dots, i_{k}$ denote the set of jobs selected by greedy.
Let $j_{1}, j_{2}, \dots, j_{m}$ denote the set of jobs in an optimal solution that agrees with the greedy solution on the most jobs with $i_{1} = j_{1}, i_{2} = i_{2}, i_{r} = j_{r}$ for largest possible value of $r$ .
We know $i_{r + 1}$ and $j_{r + 1}$ exist because the optimal solution has more jobs and there is a conflict in greedy solution causing it to not pick $j_{r + 1}$ .
The greedy solution has elements with the earliest finish time, so we can replace $j_{r + 1}$ with $i_{r + 1}$ and it would not overlap with any other elements, so the solution is still optimal.
Repeat until the solutions are equal
Therefore, the greedy solution is optimal. A contradiction. $□$

Needs dynamic algorithm