Assignment Definition
Suppose you are given a set of n jobs, where each job i has a start time si and finish time fi. We say two jobs i and j conflict if their intervals (si,fi) and (sj,fj) intersect. Your task is to design an algorithm which outputs the maximum size set of jobs such that no pair conflict. You must
1. Describe your algorithm (in plain english) 2. Prove your algorithm is correct
3. Prove the running time of your algorithm
1
A Greedy Assignment Exemplar
Patrick Eades March 2019
Describe Your Algorithm
My algorithm takes a greedy approach, by always adding the earliest finishing job to the schedule, then the next job which finishes earliest amongst jobs compatible with the current schedule, and so on.
This is done by first sorting the jobs by finishing time, so that we have f1 ≤, . . . , ≤ fn. It also keeps track of the last finishing time in the schedule, which is initialised to F = 0, and the schedule, which is a set S. Then, for each i from 1 to n, if F ≤ si, add i to the schedule S and update F to fi. Finally my algorithm outputs S.
Prove Correctness
Since my algorithm only adds jobs which start after the finish time of all the jobs which have already been added, it will never add a job which conflicts with the jobs which have already been added. Thus it must produce a feasible solution.
Let G = {g1, g2, . . . , gm} be the jobs selected by the greedy algorithm, ordered by finish time.
First I will show that G cannot be a strict subset of any optimal solution. Afterwards, I iteratively apply an exchange argument to transform an arbitrary optimal solution O into another optimal solution O′ which contains G. Since G cannot be a strict subset of O′ it follows that O′ = G and hence G is optimal.
LetObeanoptimalsolution. IfGOthenthereisajobjinOwhichisnotinG. Sincej does not conflict with anything in O and G O, j must not conflict with anything in G. Hence when j was considered by the greedy algorithm it did not conflict with any of the jobs added to G so far, and thus would thus have been added to G. This contradicts j ∈/ G and thus we know G cannot be a strict subset of O.
I will now do the exchange argument. Let O = {o1, o2, . . . , ok} be the jobs selected by some optimal solution, ordered according to finish time. Observe that m ≤ k, otherwise O would not be optimal. If G = O then G is optimal and I am done. Otherwise, because G ̸⊂ O let t be the firstindexiatwhichGandOaredifferent,i.e.gi =oi foralli