Single Threaded CPU

MEDIUM✓ CHIP-TIMEDLC #1834 — FULL STATEMENT ↗

The drill: A single CPU processes tasks by availability and duration — always run the shortest available job, and if nothing's ready yet, sit idle until the next one arrives — report the finishing order by each task's original index.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A single CPU chews through a batch of tasks, each with its own arrival time and processing duration, and always prefers the shortest available job the instant it's free to start one.

When multiple tasks have already arrived and are waiting, the CPU takes whichever has the smallest processing time, breaking any tie by picking the task with the lower original index. If nothing has arrived yet, the CPU sits idle until the next task shows up.

The output is the order tasks finish in, reported by each task's original position in the input, not by its arrival time or duration.

EX 01

tasks = [[1, 2], [2, 4], [3, 2], [4, 1]]

→ [0, 2, 3, 1]

STAGGERED ARRIVALS, NO IDLE GAPS

EX 02

tasks = [[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]]

→ [4, 3, 2, 0, 1]

ALL ARRIVE AT ONCE, PURE SHORTEST-JOB-FIRST

EX 03

tasks = [[1, 1]]

→ [0]

MINIMUM SIZE, SINGLE TASK

task counts run up to tens of thousands
arrival times and processing durations are non-negative
ties in processing time break toward the lower original index
the CPU never sits idle while any arrived task is still waiting

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Tasks don't arrive in index order or even in time order — the array you're given isn't sorted by when a task becomes available, so start by fixing that.

HINT 2 THE STRUCTURE

At any idle moment, only the ready set matters: among tasks that have already arrived, the CPU always takes whichever has the smallest processing time, ties broken by the lower original index.

HINT 3 ONE STEP FROM THE ANSWER

Sort tasks by arrival time and stream them into a min-heap keyed by (processingTime, originalIndex) as the clock passes their arrival — pop the heap, advance the clock by that duration, and repeat, jumping the clock forward whenever the heap runs dry.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE READY-QUEUE SPRINTPATTERN · MIN-HEAP BY (DURATION, INDEX)tasks by original index — arrivals [1,2,3,4] · durations [2,4,2,1]

HEAP — (DURATION, INDEX)

— empty —

STEP 1

Four tasks, durations 2, 4, 2, 1, arriving at times 1, 2, 3, 4. The CPU always grabs whichever ready task has the smallest duration.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/single-threaded-cpu.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        arrival_order = sorted(range(n), key=lambda i: tasks[i][0])
        heap = []  # (processingTime, originalIndex)
        time = 0
        i = 0
        order = []
        while len(order) < n:
            while i < n and tasks[arrival_order[i]][0] <= time:
                idx = arrival_order[i]
                heapq.heappush(heap, (tasks[idx][1], idx))
                i += 1
            if not heap:
                time = tasks[arrival_order[i]][0]
                continue
            proc, idx = heapq.heappop(heap)
            time += proc
            order.append(idx)
        return order

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 20 LN

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        done = [False] * n
        time = 0
        order = []
        remaining = n
        while remaining > 0:
            best = -1
            for i in range(n):
                if not done[i] and tasks[i][0] <= time:
                    if best == -1 or tasks[i][1] < tasks[best][1]:
                        best = i
            if best == -1:
                time = min(tasks[i][0] for i in range(n) if not done[i])
                continue
            done[best] = True
            time += tasks[best][1]
            order.append(best)
            remaining -= 1
        return order

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 21 LN

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        Integer[] arrivalOrder = new Integer[n];
        for (int i = 0; i < n; i++) {
            arrivalOrder[i] = i;
        }
        Arrays.sort(arrivalOrder, (a, b) -> tasks[a][0] - tasks[b][0]);

        PriorityQueue<int[]> heap =
                new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // [processingTime, index]
        long time = 0;
        int i = 0;
        int[] order = new int[n];
        int filled = 0;
        while (filled < n) {
            while (i < n && tasks[arrivalOrder[i]][0] <= time) {
                int idx = arrivalOrder[i];
                heap.offer(new int[] { tasks[idx][1], idx });
                i++;
            }
            if (heap.isEmpty()) {
                time = tasks[arrivalOrder[i]][0];
                continue;
            }
            int[] top = heap.poll();
            time += top[0];
            order[filled++] = top[1];
        }
        return order;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 32 LN

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        boolean[] done = new boolean[n];
        long time = 0;
        int[] order = new int[n];
        int filled = 0;
        int remaining = n;
        while (remaining > 0) {
            int best = -1;
            for (int i = 0; i < n; i++) {
                if (!done[i] && tasks[i][0] <= time) {
                    if (best == -1 || tasks[i][1] < tasks[best][1]) {
                        best = i;
                    }
                }
            }
            if (best == -1) {
                long next = Long.MAX_VALUE;
                for (int i = 0; i < n; i++) {
                    if (!done[i]) {
                        next = Math.min(next, tasks[i][0]);
                    }
                }
                time = next;
                continue;
            }
            done[best] = true;
            time += tasks[best][1];
            order[filled++] = best;
            remaining--;
        }
        return order;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 35 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED