Minimize the Worst Delay

Difficulty: 1500 5000 ms 128 MB

greedy sorting

N jobs run on one machine (no overlap); job i takes d_i time and is due at t_i. If a job finishes at time f its lateness is max(0, f − t_i). Order the jobs to minimize the MAXIMUM lateness and print that value.

Input: the first line has N; each of the next N lines has duration and deadline.

Output: the minimum possible maximum lateness.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ d_i ≤ 1000
• 1 ≤ t_i ≤ 10⁶

Sample Tests

2
3 5
2 4

0

1
5 3

2

Read the Editorial