0419MediumArraySortingHeap (Priority Queue)

Lathe Job Order

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def get_order(tasks: list[list[int]]) -> list[int]:

Java

public int[] getOrder(int[][] tasks)

The intended approach

Time O(n log n) for n jobs: one sort of the landing order, then one heap push and one heap pop per job.Space O(n) for the landing order, the heap and the returned list of job numbers.

Put the job numbers in landing order once, then sweep a clock forward. A heap holds the jobs that have landed and not run, keyed by the pair (runtime, job number), so popping it applies the lathe's rule including the tie-break directly. Before each pop, admit every job whose landing minute is at or before the clock; if nothing is waiting, move the clock straight to the next landing minute rather than ticking. Each pop advances the clock by the job's runtime.

Pythonentry point: get_order

import heapq


def get_order(tasks):
    # Walk the jobs in arrival order and keep the ones that have arrived but not
    # run in a heap keyed by (run length, job number), which is exactly the
    # lathe's choosing rule. When the heap empties the lathe is idle, so the
    # clock jumps straight to the next arrival.
    count = len(tasks)
    arrivals = sorted(range(count), key=lambda job: (tasks[job][0], job))
    waiting = []
    order = []
    clock = 0
    cursor = 0
    while len(order) < count:
        if not waiting and clock < tasks[arrivals[cursor]][0]:
            clock = tasks[arrivals[cursor]][0]
        while cursor < count and tasks[arrivals[cursor]][0] <= clock:
            job = arrivals[cursor]
            heapq.heappush(waiting, (tasks[job][1], job))
            cursor += 1
        run, job = heapq.heappop(waiting)
        clock += run
        order.append(job)
    return order

The obvious version

Simulate one start at a time. Scan every job to find the unrun one that has landed with the smallest runtime, lowest job number winning ties. When the scan finds nothing, scan again for the earliest landing minute still to come, move the clock there and repeat the search. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_get_order(tasks):
    count = len(tasks)
    done = [False] * count
    order = []
    clock = 0
    for _ in range(count):
        pick = -1
        for job in range(count):
            if done[job] or tasks[job][0] > clock:
                continue
            if pick < 0 or (tasks[job][1], job) < (tasks[pick][1], pick):
                pick = job
        if pick < 0:
            soonest = -1
            for job in range(count):
                if not done[job] and (soonest < 0 or tasks[job][0] < soonest):
                    soonest = tasks[job][0]
            clock = soonest
            for job in range(count):
                if done[job] or tasks[job][0] > clock:
                    continue
                if pick < 0 or (tasks[job][1], job) < (tasks[pick][1], pick):
                    pick = job
        done[pick] = True
        clock += tasks[pick][1]
        order.append(pick)
    return order

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in