Ctrl K

Scheduling Quad-Core Machines

Medium
There are n machines with 4 cores each. Machine i becomes free at time ready_at[i]. There are 4n tasks to run; their lengths are given in durations. Each task goes on its own core, and every core takes exactly one task. Cores run in parallel: a task of length d on machine i finishes at time ready_at[i] + d. Return the earliest time by which all tasks can be finished.
Example 1
ready_at=[3, 0], durations=[5, 1, 2, 6, 2, 4, 1, 3] → 6

The machine free at 0 gets 6, 5, 4, 3 and finishes at 6; the one free at 3 gets 2, 2, 1, 1 and finishes at 5. The answer is 6.

Example 2
ready_at=[7], durations=[2, 9, 4, 4] → 16

There is one machine, so it runs all four tasks: 7 + 9 = 16.

Example 3
ready_at=[10, 2, 5], durations=[1, 8, 3, 3, 7, 2, 6, 1, 4, 5, 2, 9] → 12
Constraints
  • 1 ≤ n = len(ready_at) ≤ 25,000
  • len(durations) = 4n
  • 0 ≤ ready_at[i] ≤ 10⁹
  • 1 ≤ durations[i] ≤ 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsBiggest Number From Pieces MediumStudios for Recording Sessions MediumLow, High, Low MediumStrictly Low, High, Low MediumFewest Meetings to Cancel Medium
loading Python…
Input
ready_at=[3, 0], durations=[5, 1, 2, 6, 2, 4, 1, 3]
Expected
6

Run checks the first 3 tests in your browser. Submit checks all 28 tests on the server, hidden ones included.