Keep the worst delay small

You work on a streaming service. A queue of new episodes waits for one encoder. Each encoding job takes some seconds, and each episode has a due time: the second, counted from when the encoder starts, at which it should be ready.

The encoder starts at second 0. It runs one job at a time, and it starts the next job as soon as one finishes. You choose the order.

An episode that finishes encoding after its due time is late by the difference. An episode that finishes on time or early has a delay of 0.

Your team lead asks: "In the best order, how late is the latest episode?"

Example 1 (traced)#

Input:  jobs = [[4, 9], [2, 15], [3, 6], [1, 9], [3, 14], [2, 8]]
Output: 1

Sort the jobs by due time, the earliest first: [3, 6], [2, 8], [4, 9], [1, 9], [3, 14], [2, 15]. Run them in that order and keep a clock.

No order does better. The four jobs due by second 9 need 3 + 2 + 4 + 1 = 10 seconds together, so one of them finishes at second 10 or later. The answer is 1.

Running the shortest job first gives a worst delay of 6 here, and running the jobs in the order given gives 7.

Example 2#

Input:  jobs = [[1, 100], [10, 10]]
Output: 0

Run the 10-second job first. It finishes at second 10, exactly when it is due. The 1-second job finishes at second 11, long before second 100.

Example 3#

Input:  jobs = [[5, 2]]
Output: 3

The only job finishes at second 5, and it was due at second 2, so it is 3 seconds late whatever you do.

• 0 ≤ len(jobs) ≤ 100,000, and every row is [seconds, due] with 1 ≤ seconds, due ≤ 1,000,000
• The clock and the answer can be larger than a 32-bit integer.