Skip to content
Get started

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)+
  1. Instead of choosing the cuts, fix a target finishing time TT and ask whether it can be met.
  2. For a fixed TT, pack each block greedily and count how many blocks you need.
  3. Start at the balanced share ⌈54/4⌉\lceil 54/4 \rceil and move up until the greedy check needs only 4 blocks.

Answer

Reveal answer →

17

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions