can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this video and i am not able to understand the proof
Algorithm - we will accept the request that finishes first. This is also quite a natural idea, we ensure that our resource becomes free as soon as possible.In this way we can maximize the time left to satisfy other requests.
let O is the set of optimal intervals and A is the set of intervals produced by our algorithm
Initially let R be the set of all requests, and let A be empty
While R is not yet empty
Choose a request i ∈ R that has the smallest finishing time
Add request i to A
Delete all requests from R that are not compatible with request i
Return the set A as the set of accepted requests
Let i1,..., ik be the set of requests in A in the order they were added to A
similarly let j1,......jm be the set of requests in O in the order they were added to O
we have to show that k $=$ m , that is both the set have same number of intervals
we want to show that our greedy rule “stays ahead” which means that each of its intervals finishes at least as soon as the corresponding interval in the set O.
which means f(ik) $\leq$ f(jK)
here f(ik) denotes the finishing time of a interval i
this statement can easily be proved using induction. base case here is the very first interval which is f(i1) $\leq$ f(j1)
Optimality - Now let's assume that k < m which means there is a interval in O which is not selected by our algorithm
let the index of that interval is k+1
we know that f(ik$+$1) $\leq$ f(jk$+$1) - based on the statement we just proved
also f(ik) $\leq$ f(ik$+$1) and f(jk) $\leq$ f(jk$+$1) - As the intervals are ordered by their finishing time
clearly jk$+$1 interval was available after jk finished but we know that ik finished before jk, so this means that an interval was available for selection after ik finished but our algorithm did not select it, but this can not happen as our algorithm will only stop when there are no intervals left.
so our assumption was wrong which means k = m
PS - I suggest reading the greedy algorithm section from the "Algorithm & Design" by Kleinberg and tardos
here is a link to a soft copy - http://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf