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.
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.
S'
contains every job of S
which finishes before its deadline.i
in S
, all jobs after i
in I_i
have a larger processing time.i
in S
, there is no idle time after i
in I_i
.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*
.