Scheduling to Minimize Maximum Lateness

Earliest-deadline order minimizes maximum lateness when every job must run, all jobs are available at zero, and one machine processes them without interruption. Lateness can be negative; tardiness clips it at zero. This problem has a different objective from profit-maximizing job selection, so sorting by profit or by duration would need entirely different proofs.

Prerequisites: Correctness via adjacent exchanges; completion times.

Build the idea

1. Define the objective precisely

   Job i has positive processing time pi and deadline di. Its completion is Ci, lateness Li=Ci−di and tardiness Ti=max(0,Li). We minimize Lmax=max Li over all jobs, with no omitted jobs. Removing idle gaps cannot increase any completion time, so it suffices to examine contiguous permutations from time zero. The empty instance convention is maximum lateness zero.

2. Order by earliest deadline

   Sort by increasing deadline, then ID for ties. Accumulate clock by duration and update the maximum of clock−deadline. Initialize maximum below all possible latenesses for a nonempty input: starting it at zero would lose a correct negative result. Print Lmax and max(0,Lmax), the corresponding maximum tardiness.

   $$\mathrm{Li}=\mathrm{Ci}-\mathrm{di};\mathrm{Ti}=\max (0,\mathrm{Li})$$

3. Correctness proof: exchange deadline inversions

   Consider adjacent jobs A,B with dA>dB beginning after time T. In the inverted order, B completes at T+pA+pB and has lateness L_B=T+pA+pB−dB. After swapping, B finishes earlier, while A’s new lateness is T+pB+pA−dA≤L_B. Other jobs are unchanged, so the pair’s maximum lateness cannot rise. Eliminate every inversion to obtain earliest-deadline order, proving it optimal.

4. Trace the sample

   Jobs (duration,deadline) are (3,4),(2,3),(1,8). Run IDs 2,1,3. Their completion times are 2,5,6 and latenesses −1,1,−2; maximum lateness and tardiness are both 1. If a single job takes 2 and is due at 10, maximum lateness is −8 while tardiness is 0. That distinction is mathematically meaningful.

   Job ID	Completion	Deadline	Lateness
   2	2	3	-1
   1	5	4	1
   3	6	8	-2

5. Keep the assumptions visible

   Release dates can make the adjacent swap illegal because a job may not be available earlier. Weighted lateness, parallel machines and precedence constraints are different models. Earliest deadline here orders all jobs; job sequencing with profits instead chooses a subset of unit jobs. Reusing the word deadline does not make their greedy rules interchangeable.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
struct Job{
    long long duration,deadline;
    int id;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Job>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].duration>>a[i].deadline;
        a[i].id=i+1;
    }
    std::sort(a.begin(),a.end(),[](Job x,Job y){
        return x.deadline!=y.deadline?x.deadline<y.deadline:x.id<y.id;
    });
    long long clock=0,maximum=n?std::numeric_limits<long long>::lowest():0;
    for(Job j:a){
        clock+=j.duration;
        maximum=std::max(maximum,clock-j.deadline);
    } // Lateness may be negative.
    std::cout<<maximum<<' '<<std::max(0LL,maximum)<<'\n';
    for(int i=0;i<n;++i){
        std::cout<<a[i].id<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n) sort and O(n) scan, O(n) job storage. Clock is at most 10^11; lateness arithmetic uses long long. Equal-deadline tie order does not affect the optimal maximum.

Example input and output

Read n (0..100000), then duration deadline with 1≤duration≤10^6 and 0≤deadline≤10^9. All jobs are available at zero and must run on one machine. Print minimum Lmax, its maximum tardiness, and job IDs in EDD order.

Input

3
3 4
2 3
1 8

Output

1 1
2 1 3

EDD gives latenesses −1,1,−2. The exchange proof shows no other order has a smaller maximum.

Practical applications

Use for worst deadline deviation in single-machine, all-available scheduling. For total completion time use shortest processing time under its assumptions. For optional unit jobs with profits, use descending-profit selection and late placement.

Check your understanding

Can an optimal maximum lateness be negative?

Put it into practice

Enumerate all orders for four jobs and compare Lmax.