Minimizing Lateness: Greedy AlgorithmGreedy algorithm. Earliest deadline first.
Sort n jobs by deadline so that d1 d2 … dn t 0 for j = 1 to n Assign job j to interval [t, t + tj] sj t, fj t + tj t t + tj output intervals [sj, fj]
max lateness = 1
d1 = 60 1 2 3
d2 = 84 5
d3 = 96 7
d4 = 98 9 10
d5 = 1411 12 13
d6 = 1514 15