Single-Threaded CPU

medium heap sorting simulation

Problem

You are given tasks[i] = [enqueueTime, processingTime]. A single-threaded CPU runs one task at a time: whenever it becomes idle, it picks the already-arrived task with the smallest processing time (smallest index breaks ties) and runs it to completion without interruption. If no task has arrived yet, the CPU idles until the next enqueue time. Return the order in which the tasks are processed.

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

Output[0, 2, 3, 1]

Task 0 runs first (t=1..3); at t=3 task 2 (dur 2) beats task 1 (dur 4); at t=5 task 3 (dur 1) beats task 1.

tasks (enqueue:duration, comma-separated)

import heapq

def get_order(tasks):
    order_idx = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
    heap = []                       # (duration, index)
    res = []
    time = 0
    i, n = 0, len(tasks)
    while len(res) < n:
        if not heap and time < tasks[order_idx[i]][0]:
            time = tasks[order_idx[i]][0]   # idle: jump to next arrival
        while i < n and tasks[order_idx[i]][0] <= time:
            j = order_idx[i]
            heapq.heappush(heap, (tasks[j][1], j))
            i += 1
        dur, j = heapq.heappop(heap)
        time += dur
        res.append(j)
    return res

function getOrder(tasks) {
  const ids = tasks.map((_, i) => i)
    .sort((a, b) => tasks[a][0] - tasks[b][0]);
  const heap = []; // [duration, index], kept min-first
  const res = [];
  let time = 0, i = 0;
  while (res.length < tasks.length) {
    if (heap.length === 0 && time < tasks[ids[i]][0])
      time = tasks[ids[i]][0]; // idle: jump to next arrival
    while (i < ids.length && tasks[ids[i]][0] <= time) {
      heap.push([tasks[ids[i]][1], ids[i]]);
      i++;
    }
    heap.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    const [dur, j] = heap.shift();
    time += dur;
    res.push(j);
  }
  return res;
}

public int[] getOrder(int[][] tasks) {
    int n = tasks.length;
    Integer[] ids = new Integer[n];
    for (int i = 0; i < n; i++) ids[i] = i;
    Arrays.sort(ids, (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]);
    int[] res = new int[n];
    long time = 0;
    int i = 0, k = 0;
    while (k < n) {
        if (heap.isEmpty() && time < tasks[ids[i]][0])
            time = tasks[ids[i]][0];        // idle: jump to next arrival
        while (i < n && tasks[ids[i]][0] <= time) {
            heap.offer(new int[]{tasks[ids[i]][1], ids[i]});
            i++;
        }
        int[] top = heap.poll();
        time += top[0];
        res[k++] = top[1];
    }
    return res;
}

vector<int> getOrder(vector<vector<int>>& tasks) {
    int n = tasks.size();
    vector<int> ids(n);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(),
         [&](int a, int b) { return tasks[a][0] < tasks[b][0]; });
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    vector<int> res;
    long long time = 0;
    int i = 0;
    while ((int)res.size() < n) {
        if (heap.empty() && time < tasks[ids[i]][0])
            time = tasks[ids[i]][0];        // idle: jump to next arrival
        while (i < n && tasks[ids[i]][0] <= time) {
            heap.push({tasks[ids[i]][1], ids[i]});
            i++;
        }
        auto [dur, j] = heap.top(); heap.pop();
        time += dur;
        res.push_back(j);
    }
    return res;
}

Explanation

The CPU's choice rule — "shortest processing time among tasks that have already arrived, smallest index on ties" — is exactly what a min-heap keyed by (duration, index) answers in O(log n). The only complication is that tasks become eligible over time, so we cannot put everything in the heap at once.

First we sort the task indices by enqueue time (the original index must be remembered because the answer is reported in original indices). A pointer i walks this sorted list and acts as a release gate: every task whose enqueue time is ≤ the current clock gets pushed into the heap as a (duration, index) pair.

The simulation loop then alternates two moves. If the heap is empty and the next task arrives in the future, the CPU is idle, so we fast-forward the clock to that arrival instead of ticking one unit at a time. Otherwise we release all newly arrived tasks, pop the heap top, run it to completion (time += duration), and append its index to the answer.

Walking the default example [[1,2],[2,4],[3,2],[4,1]]: the clock jumps to t=1 and task 0 runs until t=3. By then tasks 1 and 2 have arrived; task 2 is shorter (2 vs 4) so it runs until t=5, releasing task 3 along the way. Task 3 (dur 1) beats task 1 (dur 4) and runs until t=6, and task 1 finishes last — order [0, 2, 3, 1].

Every task is pushed and popped exactly once, and the initial sort dominates: O(n log n) time overall with O(n) extra space for the sorted index list and the heap. The clock jump is what keeps the runtime independent of how large the timestamps are.

Time: O(n log n) Space: O(n)