0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Could you add in the question which explanation of that algorithm you have read? That is the least you should do. What is better, can you identify the very first statement where you got confused or lost in that explanation? People will be able to help you faster and better then. $\endgroup$ – Apass.Jack Nov 1 '18 at 14:40
0
$\begingroup$

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

formally: 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 EndWhile 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.