The problem
One machine runs jobs one after another, starting at time 0, with no gaps. Each job is a pair (length, deadline). A job that finishes at time f is late by max(0, f - deadline). Choose the order of the jobs so that the largest lateness is as small as possible, and return that largest lateness.
least_lateness([(3, 6), (2, 2), (1, 9), (4, 8)])
# 1: run (2, 2), (3, 6), (4, 8), (1, 9);
# they finish at 2, 5, 9 and 10
Return 0 when every job can finish on time, and for an empty list. Lengths are at least 1; deadlines are at least 0.
Limits
- Up to 200,000 jobs. Trying every order is impossible; aim for O(n log n).
Builds on GRDY-2 Exchange arguments.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | All on time | Not run | |
| 3 | No jobs | Not run | |
| 4 | One late job | Not run | |
| 5 | Shortest first is wrong | Not run | |
| 6 | Least slack first is wrong | Not run | |
| 7 | Same deadlines | Not run | |
| 8 | Deadline 0 | Not run | |
| 9 | Nine jobs | Not run | |
| 10 | 200,000 jobs | Not run |