Get started

Single-Threaded CPU — Medium Problem & Solution

tasks[i] = [enqueueTime, processingTime] means task i becomes available at enqueueTime and takes processingTime to run.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Heap
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

tasks[i] = [enqueueTime, processingTime] means task i becomes available at enqueueTime and takes processingTime to run. The CPU runs one task at a time and never pauses one it has started.

When the CPU is free it picks the available task with the shortest processing time, breaking ties by the smaller index. If nothing is available it idles until something is. Return the order in which the tasks are processed, as a list of indices.

Example 1

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: At time 3 both tasks 1 and 2 wait; task 2 is shorter.

Example 2

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: All arrive together, so they run shortest first.

Example 3

Input: tasks = [[1,1]]
Output: [0]

Constraints

  • tasks.length == n
  • 1 <= n <= 10^5
  • 1 <= enqueueTime, processingTime <= 10^9

How to solve Single-Threaded CPU

Simulate the CPU. Sort by enqueue time, release everything that has arrived by the current clock into a min-heap ordered by processing time then index, and always start the heap's top.

Approach

  1. Sort the task indices by enqueue time.
  2. Release every task whose enqueue time is at most the clock.
  3. If nothing is available, set the clock to the next task's enqueue time and release again.
  4. Otherwise pop the shortest task, advance the clock by its processing time, and record its index.

Why it works

Jumping the clock straight to the next enqueue time is what keeps this linear rather than tied to the 10^9 time range — the CPU's state only ever changes at an arrival or a completion. The (processingTime, index) key encodes the tie-break directly, so no second comparison is needed after the pop.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Ticking the clock one unit at a time is far too slow at 10^9.
  • Ties go to the smaller original index, not the smaller position in the sorted order.
  • Tasks that arrive while one is running must be released before the next pick.

Reference solution

Python

from typing import List
import heapq

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

JavaScript

var getOrder = function(tasks) {
    var n = tasks.length, i;
    var order = [];
    for (i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return tasks[a][0] - tasks[b][0]; });
    // Min-heap of task indices ordered by (processingTime, index).
    var heap = [];
    var less = function(a, b) {
        if (tasks[a][1] !== tasks[b][1]) return tasks[a][1] < tasks[b][1];
        return a < b;
    };
    var push = function(v) {
        heap.push(v);
        var j = heap.length - 1;
        while (j > 0) {
            var p = (j - 1) >> 1;
            if (!less(heap[j], heap[p])) break;
            var t = heap[p]; heap[p] = heap[j]; heap[j] = t;
            j = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var j = 0;
            for (;;) {
                var l = 2 * j + 1, r = l + 1, s = j;
                if (l < heap.length && less(heap[l], heap[s])) s = l;
                if (r < heap.length && less(heap[r], heap[s])) s = r;
                if (s === j) break;
                var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
                j = s;
            }
        }
        return top;
    };
    var out = [];
    var at = 0, time = 0;
    while (out.length < n) {
        while (at < n && tasks[order[at]][0] <= time) { push(order[at]); at++; }
        if (heap.length === 0) {
            time = tasks[order[at]][0];
            continue;
        }
        var pick = pop();
        time += tasks[pick][1];
        out.push(pick);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue