The task is to schedule $n$ jobs to minimize the maximum lateness. Each job, $i$, has a deadline $d_i$ and a time $t_i$ which it requires to complete. The lateness of job $i$, $l_i$ is defined as $l_i = \max(0, s_i + t_i - d_i)$, where $s_i$ is the start time of job $i$ ($s_i$ is to be decided by the algorithm).
Ordering the jobs by smallest deadline first is optimal. I am writing the proof for this. The idea is that if we have an inversion ($i$ scheduled after $j$, but $d_i < d_j$), then we can swap $i$ and $j$, without increasing the maximum lateness and decreasing the number of inversions by $1$. So if we start with an optimal schedule with inversions, then we can transform it into an optimal schedule without inversions (what the greedy algorithm outputs).
I am at the stage where I have shown that if we have an inversion, then we must have an inversion between consecutive jobs. I have also shown that if we swap consecutive inverted jobs, the maximum lateness does not increase.
What remains is showing that if I swap $2$ consecutive inverted elements, the total number of inversions decreases by $1$.
Let the two consecutive jobs be $i$ and $j$, such that $i < j$ and they are inverted. Let $a_l$ be a job to the left of $j$ and $a_r$ be a job to the right of $i$. All I can think of doing is showing that:
- if $a_l$ and $i$ are inverted, then they are inverted after swapping $i$ and $j$.
- if $a_r$ and $i$ are inverted, then they are inverted after swapping $i$ and $j$.
- if $a_l$ and $j$ are inverted, then they are inverted after swapping $i$ and $j$.
- if $a_r$ and $j$ are inverted, then they are inverted after swapping $i$ and $j$.
This method of exhausting all possible scenarios seems really ugly, is there a more general argument for why swapping to inverted elements decreases the number of inversions by $1$?
Perhaps using contradiction would work (suppose swapping inverted elements causes the total number of inversions to stay unchanged).