Interval Scheduling

With given intervals, want to maxmize possible nubmer of intervals by scheduling

Greedy algorthim

1. Use a simple rule to select a request i

2. Reject all requests imcompatible with i

3. Repeat until all request are processed // basic template but no rules we need to specifiy the rules

Possible rules 

1. Select request that start earliest 

2. Select request that has smallest interval

3. For each request find # incompatibles select the one with minimum # incompatible

4. Select request with earliest finish time // this one doesn't have a counter example ,need to prove

Claim 1

s(i) = starting time f(i) = finshing time

Claim 2

Given list of intervals L, greedy algorithm with earliset finish time produces k* intervals, where k* is optimal.

Proof. Induction on k*
 Base case : k* = 1  -- this case any interval would work
 Inductive step : Suppose claim holds for k* and we are given a list of intervals whose optimal schedule has k*+1 intervals, namely 

Optimal Solution But we are not certain that this used earliest finish time

Created example with Earliest finish time greedy heuristic 

By construction, we know that f(i1) ≤ f(j1), since the greedy algorithm picks the earliest finish time. but optimal might have not used earliest finish time! 

Only first part is exchanged rest of terms are same And still OPTIMAL because it still produce k*+1

Define L' as the set of intervals with s(i) ≥ f(i1). // same as rejecting all the incompatiable interval 

Since S** is optimal for L, S**[2, 3, . . . , k* + 1] is optimal for L' , which implies that the optimal schedule for L' has k* size. // Subset of optimal solution has to be optimal if not i can select something better and shrink k to something less which is contradiction 

By inductive hypothesis that running the greedy algorithm on L' should produce a schedule of size k*. 

Running the greedy algrothim(above Created example)  on L' gives us S[2, ... ,k].  ==  k-1 size

This means k-1 == k*  also k == k* + 1 which implies that S[1 ... k] is optimal  

 

Reference == 

1. Course Overview, Interval Scheduling - YouTube