Smallest Maximum Lateness
Job i takes durations[i] minutes and is due at minute deadlines[i]. Starting at minute 0 you do the jobs one at a time with no breaks, in an order of your choice. A job's lateness is how many minutes after its deadline it finishes, or 0 if it finishes on time (finishing exactly at the deadline is on time). Return the smallest value that the largest lateness among all jobs can have.
Example 1
Doing the jobs in deadline order finishes them at minutes 3, 5 and 6, all on time, so the largest lateness is 0.
Example 2
Deadline order does the 4-minute job first (late by 2) and the 2-minute job second, finishing at 6 (late by 2). The other order makes the 4-minute job late by 4.
Constraints
1 <= len(durations) == len(deadlines) <= 1001 <= durations[i] <= 1000 <= deadlines[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.