Show problems as
Classic problem #1834MediumArraySortingHeap (Priority Queue)

Single-Threaded CPU

Real-world version: Lathe Job Order
Tracked in this browser only
Read Single-Threaded CPU on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A machine shop owns one lathe, and tasks.length jobs are booked on it. Job i is described by tasks[i] = [arrival_i, runtime_i]: the work order lands on the bench at minute arrival_i, and once the lathe starts it the job occupies the lathe for runtime_i minutes without a break.

The lathe never runs two jobs at once and is never stopped part way through a job. It follows one rule whenever it becomes free, and also at the very start:

  • Of the jobs whose work order has landed and which have not been run yet, it starts the one with the smallest runtime_i. If several share the smallest runtime, it starts the one with the lowest job number.
  • If no unrun work order has landed yet, the lathe stands idle and starts the next order to land the moment it lands.

A work order that lands at exactly the minute the lathe becomes free counts as having landed and may be started right then.

Return the job numbers in the order the lathe starts them.

Examples

Example 1

Input
tasks = [[1, 4], [3, 2], [4, 1]]
Output
[0, 2, 1]

At minute 1 only job 0's order has landed, so the lathe takes it and is busy until minute 5. By then both remaining orders have landed, and job 2 needs one minute against job 1's two, so job 2 goes on next and job 1 last.

Example 2

Input
tasks = [[1, 2], [10, 1]]
Output
[0, 1]

Job 0 runs from minute 1 to minute 3. Nothing else has landed, so the lathe stands idle until job 1's order arrives at minute 10.

Example 3

Input
tasks = [[1, 3], [1, 1], [1, 2]]
Output
[1, 2, 0]

All three orders land at minute 1. Job 1 needs one minute, job 2 needs two, job 0 needs three, and the lathe works through them in that order.

Example 4

Input
tasks = [[1, 5], [1, 5], [1, 5]]
Output
[0, 1, 2]

The three orders land together and all ask for five minutes, so the lowest job number wins each time.

Example 5

Input
tasks = [[1, 3], [4, 1], [2, 5]]
Output
[0, 1, 2]

Job 0 runs from minute 1 to minute 4. Job 1's order lands exactly at minute 4, so it is in the running alongside job 2 and its single minute is the shorter of the two.

Constraints

  • 1 <= tasks.length <= 10^5
  • tasks[i].length == 2
  • 1 <= arrival_i <= 10^9
  • 1 <= runtime_i <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def get_order(tasks: list[list[int]]) -> list[int]:
Java
public int[] getOrder(int[][] tasks)

More on the same topics