What is the optimality proof of the earliest finish time algorithm?

  • Thread starter lolo94
  • Start date
  • Tags Tags
    Proof
1 reply · 2K views · last reply
lolo94
Messages
17
Reaction score
0

Homework Statement


I am trying to understand the optimality proof of the earliest finish time algorithm. I have attached the pdf which I am reading. It's just 2 pages. I don't understand what they mean with solution still feasible and optimal (but contradicts maximality of r). An explanation from scratch would be nice...

Homework Equations

The Attempt at a Solution

 
Attachments
  • Slide diagram of the greedy proof for interval scheduling: top row Greedy jobs i1, i2, ir, ir+1, ik and bottom row OPT jobs j1, j2, jr, jr+1, jm, with a note that job ir+1 exists and finishes before jr+1.
    Screenshot (25).png
    29.9 KB · Views: 493
  • Slide proof diagram comparing Greedy and OPT rows of job intervals i1 to ik and j1 to jm, with job i_{r+1} finishing before j_{r+1} and a note that the OPT solution is still feasible and optimal.
    Screenshot (26).png
    40.2 KB · Views: 512
The proof supposes that the greedy algorithm matches the optimal solution, in regard to job finish times, up to and including the first r jobs, but not the first r+1. Clearly, if greedy is not optimal, there must be such an r, 0<=r<n. Note that optimal here just means that the finish time of the nth job is as early as it could be.
In the second diagram, the r+1th job finishes at the same time in both greedy and optimal. That contradicts the definition of r, since it was defined to be such that greedy was not as good as optimal at the r+1th job.