Single-Threaded CPU

Medium
968.

Single-Threaded CPU

MediumArraySortingHeap (Priority Queue)AmazonGoogleUber

Single-Threaded CPU is a medium coding problem on arrays, sorting and heap, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} tasks
 * @return {number[]}
 */
var getOrder = function(tasks) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Single-Threaded CPU — Solution in Python, Java & C++

Single-Threaded CPU solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Single-Threaded CPU is a medium coding problem on arrays, sorting and heap, asked in Amazon, Google and Uber interviews.

  • 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

Hints for Single-Threaded CPU

  1. Hint 1

    Sort the tasks by enqueue time so they can be released in order.

  2. Hint 2

    Keep the released-but-unstarted tasks in a min-heap keyed on (processingTime, index).

  3. Hint 3

    When the heap is empty, jump the clock forward to the next enqueue time rather than ticking.

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

Java

public static int[] getOrder(int[][] tasks) {
    int n = tasks.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(tasks[a][0], tasks[b][0]));
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> {
        if (tasks[a][1] != tasks[b][1]) return Integer.compare(tasks[a][1], tasks[b][1]);
        return a - b;
    });
    int[] out = new int[n];
    int cnt = 0, at = 0;
    long time = 0;
    while (cnt < n) {
        while (at < n && tasks[order[at]][0] <= time) heap.add(order[at++]);
        if (heap.isEmpty()) {
            time = tasks[order[at]][0];
            continue;
        }
        int pick = heap.poll();
        time += tasks[pick][1];
        out[cnt++] = pick;
    }
    return out;
}

C++

vector<int> getOrder(vector<vector<int>>& tasks) {
    int n = (int) tasks.size();
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return tasks[a][0] < tasks[b][0]; });
    auto cmp = [&](int a, int b) {
        if (tasks[a][1] != tasks[b][1]) return tasks[a][1] > tasks[b][1];
        return a > b;
    };
    priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);
    vector<int> out;
    int at = 0;
    long long time = 0;
    while ((int) out.size() < n) {
        while (at < n && tasks[order[at]][0] <= time) heap.push(order[at++]);
        if (heap.empty()) {
            time = tasks[order[at]][0];
            continue;
        }
        int pick = heap.top();
        heap.pop();
        time += tasks[pick][1];
        out.push_back(pick);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms