Proof of optimality of a greedy solution to job sequencing

Question

In this Job Sequencing Problem, how do we prove that the solution which greedy approach will provide is a optimal one?

Moreover, I am also not able to figure out the O(n) solution as the author later is claiming

It can be optimized to almost O(n) by using union-find data structure.

Answer 1

The optimality of the greedy solution can be seen by an exchange argument as follows. Without loss of generality, assume that all profits are different and that the jobs are sorted in decreasing order of profits.

Fix a solution S. From this solution, delete every job that misses its deadline. As by this transformation every job finishes within its deadline, the resulting solution S1 is still optimal. For job i, consider the interval I_i:=[0,min(n,deadline(i))] (as in the greedy algorithm). In this interval, to the right of job i, there are only jobs with larger processing time (if not, they either would have been considered earlier by our ordering, or they could be exchanged witout violation of their deadlines). Place job i to the rightmost position possible in I_i.

In total, we have the following statement.

Each solution S can be transformed into a solution S' with the following propoerties.

1. S' contains every job of S which finishes before its deadline.
2. For every job i in S, all jobs after i in I_i have a larger processing time.
3. For every job i in S, there is no idle time after i in I_i.
4. S' has the same objective value as S.

In particular, there exists an optimal solution S* with the properties above. Let S be the algorithm generated by the greedy algorithm. Note that S also has the properties 2 and 3 above. Let i be the first job which occurs in S but not in S*. Let pos be the time slot of i in S. If pos was empty in S*, S* could be improved by adding i, in contradiction to the optimality of S*. If pos was not empty in S*, the job i'at pos in S* cannot be of larger profit than i, since otherwise the greedy algorithm would have chosen i' to be at pos in S. Hence, it must be of lower profit than i. This means that it can be deleted and replaced by i in S*, which also contradicts the optimality of S*.