Single-Threaded CPU

NeetCode: Single-Threaded CPU · LeetCode: 1834. Single-Threaded CPU · Difficulty: Medium

You are given tasks, where tasks[i] = [enqueueTime, processingTime]. A single CPU runs them under these rules: if it is idle and no task is available, it waits until one is enqueued. If it is idle and several tasks are available, it picks the one with the shortest processing time, breaking ties by the smaller index. Once started, a task runs to completion, and the CPU can start the next task at the instant the previous one finishes. Return the order in which the CPU processes the tasks.

Example

Text

Input:  tasks = [[1,2],[2,4],[3,2],[4,1]]   Output: [0,2,3,1]
Input:  tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]   Output: [4,3,2,0,1]

In the first example, task 0 runs from time 1 to 3. At time 3 tasks 1 and 2 are waiting and task 3 (enqueued at time 4) has not arrived yet, so task 2 (length 2) runs from 3 to 5. At time 5, tasks 1 (length 4) and 3 (length 1) are available, so task 3 runs, then task 1.

Enqueue times and processing times can each be as large as 10^9, and the clock is their running sum, so the clock is a long. An int clock would wrap around silently.

Brute force: rescan every task at each step

Keep the current time. To choose the next task, scan all tasks that are unfinished and already enqueued, and take the best by (processing time, index). If there is none, jump the clock to the earliest enqueue time among the unfinished tasks. The scan visits indices in increasing order and replaces the best only on a strictly shorter task, so ties keep the smaller index.

Java

import java.util.Arrays;

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {{1, 2}, {2, 4}, {3, 2}, {4, 1}})));
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {{7, 10}, {7, 12}, {7, 5}, {7, 4}, {7, 2}})));
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {{1, 1}, {100, 1}})));
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {})));
    }
}

Output

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

Each of the n steps scans all n tasks. Time: O(n^2). Space: O(n).

Optimal: sort by enqueue time, min-heap of available tasks

Sort task indices by enqueue time once. Then sweep: whenever the clock reaches a task's enqueue time, push it on a min-heap keyed by (processing time, index). If the heap is empty, jump the clock to the next enqueue time. Otherwise pop the best task, run it, and advance the clock. Each task is pushed and popped once.

PriorityQueue is a min-heap, so the comparator orders by processing time and then by index; the second key gives the tie-break. Integer.compare is used instead of subtraction, which can overflow. A PriorityQueue of int[] pairs holds {processing time, index}. Sorting needs an Integer[] of indices, because Arrays.sort with a comparator does not accept int[].

Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

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

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) ->
                a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        int[] order = new int[n];
        int count = 0;
        long time = 0;
        int next = 0;
        while (count < n) {
            if (heap.isEmpty() && next < n) {
                time = Math.max(time, tasks[byEnqueue[next]][0]);
            }
            while (next < n && tasks[byEnqueue[next]][0] <= time) {
                int i = byEnqueue[next];
                heap.add(new int[] {tasks[i][1], i});
                next++;
            }
            int[] top = heap.poll();
            time += top[0];
            order[count++] = top[1];
        }
        return order;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {{1, 2}, {2, 4}, {3, 2}, {4, 1}})));
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {{7, 10}, {7, 12}, {7, 5}, {7, 4}, {7, 2}})));
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {{1, 1}, {100, 1}})));
        System.out.println(Arrays.toString(solution.getOrder(new int[][] {})));
    }
}

Output

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

Arrays.sort on objects is stable, but the heap key already includes the index, so ties never depend on sort order. After the first push in each loop pass the heap is never empty: either it already held a task, or the clock jumped to the next enqueue time and that task was pushed. Time: O(n log n) for the sort and the heap operations. Space: O(n).