Cutting a job queue across four machines
Ten backtest jobs must run in the order given; their run times in minutes are
4, 8, 3, 6, 5, 9, 2, 7, 4, 6.
You have 4 identical machines that all start at once. The list must be cut into 4 consecutive, non-empty blocks, one block per machine (a machine runs its block's jobs back to back). What is the smallest possible time, in minutes, until the last machine finishes?
Show hints (3)+
- Instead of choosing the cuts, fix a target finishing time and ask whether it can be met.
- For a fixed , pack each block greedily and count how many blocks you need.
- Start at the balanced share and move up until the greedy check needs only 4 blocks.
Answer
Reveal answer →Final answer
17
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading