Single-Threaded CPU
Problem
i is [enqueueTime, processingTime]. A single CPU runs
one task at a time to completion. Whenever it is free, it picks, among tasks that have
already arrived, the one with the shortest processing time (ties → smaller
index); if nothing has arrived it idles until something does. Return the order in which
task indices are processed.[[1,2],[2,4],[3,2],[4,1]]Output[0,2,3,1][[7,10],[7,12],[7,5],[7,4],[7,2]]Output[4,3,2,0,1]1 ≤ n ≤ 105 · 1 ≤ enqueueTime, processingTime ≤ 109
Try it yourself
class Solution {
public int[] getOrder(int[][] tasks) {
}
}
Instinct "K largest / smallest / closest / most frequent", or "always take the best available next"? Keep a heap - size k for top-K, or a ready-queue for scheduling.
Memory hack Guard the top-K club with a bouncer - a min-heap of size k whose root is the weakest member; anyone stronger kicks them out.
Open the Heap & Top-K guide →Approaches
Brute ForceRescan All Tasks per Pick
O(n2)Space O(n)Simulate directly. Before each pick, move the clock forward to the earliest
pending arrival if the CPU would otherwise idle. Then scan every pending task and
take the arrived one with the smallest processing time — scanning indices in
ascending order with a strict < resolves ties by index.
public int[] getOrder(int[][] tasks) { int n = tasks.length; boolean[] done = new boolean[n]; int[] order = new int[n]; long time = 0; // can exceed int range for (int k = 0; k < n; k++) { long earliest = Long.MAX_VALUE; for (int i = 0; i < n; i++) if (!done[i]) earliest = Math.min(earliest, tasks[i][0]); time = Math.max(time, earliest); // idle until something arrives int pick = -1; for (int i = 0; i < n; i++) { if (!done[i] && tasks[i][0] <= time && (pick == -1 || tasks[i][1] < tasks[pick][1])) pick = i; } done[pick] = true; order[k] = pick; time += tasks[pick][1]; } return order; }
Obviously correct, but 105 tasks means ~1010 steps.
OptimalSort by Arrival + Min-Heap
O(n log n)Space O(n)Sort task indices by enqueue time. Loop: if the heap is empty and the next task
hasn't arrived, jump time to its arrival; push every task with
enqueue ≤ time into a min-heap ordered by (processing, index); poll
one, record it, add its processing time. Each task is pushed and polled once.
public int[] getOrder(int[][] tasks) { int n = tasks.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> Integer.compare(tasks[a][0], tasks[b][0])); PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> tasks[a][1] != tasks[b][1] ? Integer.compare(tasks[a][1], tasks[b][1]) : Integer.compare(a, b)); int[] order = new int[n]; long time = 0; // up to ~10^14 int i = 0, k = 0; while (k < n) { if (pq.isEmpty() && time < tasks[idx[i]][0]) time = tasks[idx[i]][0]; // idle jump while (i < n && tasks[idx[i]][0] <= time) pq.offer(idx[i++]); int t = pq.poll(); order[k++] = t; time += tasks[t][1]; } return order; }
Each task costs O(log n) heap work — scales to 105 tasks.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Rescan All Tasks per Pick | O(n2) | O(n) |
| Optimal | Sort by Arrival + Min-Heap | O(n log n) | O(n) |
- Keeping the clock in an
int— 105 tasks × 109 overflows. - Advancing time by 1 when idle instead of jumping to the next arrival — TLE.
- Sorting by processing time up front — ignores which tasks have actually arrived.
- Name the two keys: availability (sorted list) vs priority (heap).
- Walk through the idle case explicitly — it is where most bugs hide.
- Note this is Shortest-Job-First scheduling; mention Task Scheduler / meeting-room variants.