Single-Core Job Runner
MediumHeap / Priority Queue
Problem
A single-core machine receives jobs; jobs[i] = [arrival, duration] means job i becomes available at time arrival and needs duration uninterrupted time units. The machine starts at time 0 and follows these rules:
When it is idle and at least one job is available, it starts the available job with the shortest duration, breaking ties by the smallest index, and runs it to completion. When it is idle and nothing is available, it waits for the next arrival. A job that arrives exactly when another finishes is available at that moment.
Return the indices of the jobs in the order the machine runs them.
Example 1
- Input:
- jobs = [[1, 3], [2, 1], [2, 4], [3, 2]]
- Output:
- [0, 1, 3, 2]
t=1: only job 0 → runs until 4. At t=4 jobs 1 (1), 2 (4), 3 (2) are waiting: run 1 (until 5), then 3 (until 7), then 2.
Example 2
- Input:
- jobs = [[0, 5], [0, 5], [0, 1]]
- Output:
- [2, 0, 1]
All arrive at 0. Job 2 is shortest; jobs 0 and 1 tie on duration, so index 0 goes first.
Constraints
- 1 ≤ jobs.length ≤ 10^5
- 0 ≤ arrival ≤ 10^9
- 1 ≤ duration ≤ 10^9
Hint
Show the first hint
Jobs become available in order of arrival, regardless of their index. Process them in that order.
Walkthrough
How to approach it
01Clarify before coding
- Is the job preemptive? No: once started it runs to completion.
- Is a job arriving exactly at the finish time available? Yes.
- Can times be large? Up to 10^9, and sums up to about 10^14: fine in Python and in JavaScript numbers.
02Brute force
Each time the machine is free, scan all unfinished jobs to find the available one with the smallest (duration, index).
Cost: O(n²): 10^10 comparisons for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.