The problem
There are m identical machines and a list of job lengths. Each job runs on one machine, and each machine runs its jobs one after another. Return, for each job in the given order, the number of its machine (0 to m − 1). The busiest machine’s total must be at most 4/3 of the smallest possible.
schedule([1, 1, 1, 1, 1, 1, 3], 3)
# for example [1, 1, 1, 2, 2, 2, 0]:
# each machine then has a total of 3, the best possible
Many answers are right. Each test checks only that your list is a valid assignment and that the busiest total is at most 4/3 of the best possible (known for each test).
Limits
- Up to 200,000 jobs and 10,000 machines. Finding the least loaded machine by looking at all of them, for every job, is too slow.
Builds on HARD-4 Approximation algorithms.
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 | One machine | Not run | |
| 2 | More machines than jobs | Not run | |
| 3 | In the given order is not enough | Not run | |
| 4 | Two machines | Not run | |
| 5 | Graham's example | Not run | |
| 6 | Random jobs | Not run | |
| 7 | Equal jobs | Not run | |
| 8 | 200,000 jobs on 10,000 machines | Not run | |
| 9 | Few machines, many jobs | Not run |