1104. The Latest Anything Runs

One machine starts at time 0 and never idles. Job i takes p units of work and is DUE at time d. If a job finishes at time C, its lateness is C - d, which is negative when it finishes early.

Every job must be run, in an order you choose. Print the smallest possible value of the LARGEST lateness over all jobs.

jobs (3,6) (2,8) (1,9) (4,9) -> 1 jobs (5,100) -> -95 the only job finishes 95 units early jobs (10,3) -> 7 it cannot possibly be on time jobs (2,2) (2,4) (2,6) -> 0 everything lands exactly on its due date

Trace the first line. Sorted by due date the jobs are (3,6), (2,8), (1,9), (4,9). They finish at 3, 5, 6 and 10, so their latenesses are 3 - 6 = -3, 5 - 8 = -3, 6 - 9 = -3 and 10 - 9 = 1. The largest is 1, and no order does better.

## What most people try first

Running the SHORTEST job first, which is right for problem #1102 and wrong here. On (3,6) (2,8) (1,9) (4,9) shortest-first gives the order (1,9), (2,8), (3,6), (4,9), finishing at 1, 3, 6, 10, with latenesses -8, -5, 0, 1. The largest is still 1, so that input does not separate them; (5,5) (1,1) does. Shortest-first runs the one-unit job first, finishing at 1 with lateness 0, then the five-unit job at 6 with lateness 1, giving 1. Due-date order runs (1,1) first too, since 1 is the earlier due date, so try (1,10) (5,5): shortest-first gives lateness max(1-10, 6-5) = 1, due-date order gives max(5-5, 6-10) = 0. The tests contain that shape.

Trying every order costs n!.

## The method

Sort by DUE DATE ascending and run in that order, tracking the clock.

sort jobs by d ascending clock = 0 worst = minus infinity for (p, d) in that order: clock = clock + p worst = max(worst, clock - d)

One sort and one pass. This is the earliest-due-date rule.

## Why due-date order is optimal

Take an optimal order that is not sorted by due date. Somewhere two ADJACENT jobs are inverted: job a runs immediately before job b and d_a > d_b. Let S be the time the pair starts.

Nothing outside the pair changes when they swap, because the pair still occupies S to S + p_a + p_b.

Before the swap the two latenesses are S + p_a - d_a and S + p_a + p_b - d_b. After the swap they are S + p_b - d_b and S + p_a + p_b - d_a.

Compare the maxima. The largest of the two AFTER values is at most S + p_a + p_b - d_a, since S + p_b - d_b < S + p_a + p_b - d_b requires nothing and S + p_b - d_b <= S + p_a + p_b - d_a follows from d_a > d_b together with p_a >= 0. And S + p_a + p_b - d_a is strictly smaller than the BEFORE value S + p_a + p_b - d_b, again because d_a > d_b.

So the swap does not increase the largest lateness. Repeating it as a bubble sort turns any order into due-date order without ever making the answer worse, so due-date order is optimal.

## The boundary that breaks a careless implementation

The answer can be NEGATIVE, and often is. Starting the running maximum at 0 reports 0 for (5,100) where -95 is correct. Start it at the first job's lateness, or at a value below anything possible.

Ties in due date do not matter: two jobs with the same due date can be run in either order without changing the answer, which the proof above covers since it only needs d_a > d_b to act.

## Sizes

n reaches 2 * 10^5 and p reaches 10^9, so the clock reaches 2 * 10^14 and the lateness reaches the same magnitude. That is far past the 2147483647 limit of a signed 32-bit integer. Even three jobs of 10^9 push the clock to 3 * 10^9, which is what the last test does.

## A related problem

Problem #1106 keeps the same input shape and asks a different question: rather than running everything and minimising the worst lateness, choose the largest set of jobs that are ALL on time. That one needs a heap and an eviction rule; this one needs only the sort.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ p ≤ 1000000000` - `0 ≤ d ≤ 1000000000`