Single-Threaded CPU - Practice Coding Problems

Single-Threaded CPU - Problem

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_i to finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Input & Output

Example 1 — Basic Task Scheduling

$ Input: tasks = [[1,2],[2,4],[3,2]]

› Output: [0,1,2]

💡 Note: At time 1, only task 0 is available with processing time 2. At time 3, task 1 becomes available with processing time 4. At time 7, task 2 becomes available with processing time 2. Tasks are processed in the order they become available.

Example 2 — Priority by Processing Time

$ Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]

› Output: [4,3,2,0,1]

💡 Note: All tasks are available at time 7. They are processed in order of shortest processing time: task 4 (2 time), task 3 (4 time), task 2 (5 time), task 0 (10 time), task 1 (12 time).

Example 3 — Mixed Timing

$ Input: tasks = [[1,2],[2,1],[3,3]]

› Output: [0,2,1]

💡 Note: Time 1: process task 0 (2 units) → finishes at time 3. Time 3: tasks 1 and 2 both available, task 1 has shorter processing time (1 < 3), so process task 1 first → finishes at time 4. Time 4: process task 2.

Constraints

1 ≤ tasks.length ≤ 10⁵
1 ≤ enqueueTime_i, processingTime_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Tasks with [enqueueTime, processingTime]: [[1,2], [2,4], [3,2]]

Process

CPU picks shortest processing time among available tasks

Output

Order of task execution: [0, 1, 2]

Key Takeaway

🎯 Key Insight: Sort tasks by enqueue time, then use a priority queue to always select the shortest processing time among available tasks

Asked in

G Google 25 a Amazon 20 M Microsoft 15 🍎 Apple 12

The key insight is to sort tasks by enqueue time and use a priority queue to efficiently select the task with shortest processing time among available tasks. The optimal approach achieves O(n log n) time complexity with O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Sort by Enqueue Time + Priority Queue	O(n log n)	O(n)	Sort tasks by enqueue time, then use min-heap to pick shortest processing time
Brute Force Simulation	O(n² × maxTime)	O(n)	Simulate time step by step, checking all available tasks each time

Sort by Enqueue Time + Priority Queue — Algorithm Steps

Sort tasks by enqueue time with original indices
Use priority queue for available tasks
Process tasks in order, adding newly available ones to heap
Always pick task with shortest processing time

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort tasks by enqueue time: [1,2], [2,4], [3,2]

Heap

Use min-heap to always pick shortest processing time

Process

Process tasks in optimal order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int processingTime;
    int index;
} Task;

typedef struct {
    int enqueueTime;
    int index;
} SortedTask;

int compareSorted(const void* a, const void* b) {
    return ((SortedTask*)a)->enqueueTime - ((SortedTask*)b)->enqueueTime;
}

int compareTask(const void* a, const void* b) {
    Task* ta = (Task*)a;
    Task* tb = (Task*)b;
    if (ta->processingTime != tb->processingTime) {
        return ta->processingTime - tb->processingTime;
    }
    return ta->index - tb->index;
}

int* solution(int** tasks, int tasksSize, int* returnSize) {
    // Sort tasks by enqueue time
    SortedTask* sortedTasks = (SortedTask*)malloc(tasksSize * sizeof(SortedTask));
    for (int i = 0; i < tasksSize; i++) {
        sortedTasks[i].enqueueTime = tasks[i][0];
        sortedTasks[i].index = i;
    }
    qsort(sortedTasks, tasksSize, sizeof(SortedTask), compareSorted);
    
    int* result = (int*)malloc(tasksSize * sizeof(int));
    Task* availableHeap = (Task*)malloc(tasksSize * sizeof(Task));
    int heapSize = 0;
    int resultCount = 0;
    int currentTime = 0;
    int taskIdx = 0;
    
    while (resultCount < tasksSize) {
        // Add all tasks that are available at currentTime
        while (taskIdx < tasksSize && sortedTasks[taskIdx].enqueueTime <= currentTime) {
            int origIdx = sortedTasks[taskIdx].index;
            availableHeap[heapSize].processingTime = tasks[origIdx][1];
            availableHeap[heapSize].index = origIdx;
            heapSize++;
            taskIdx++;
        }
        
        if (heapSize > 0) {
            // Find minimum task (simple linear search for this implementation)
            int minIdx = 0;
            for (int i = 1; i < heapSize; i++) {
                if (availableHeap[i].processingTime < availableHeap[minIdx].processingTime ||
                    (availableHeap[i].processingTime == availableHeap[minIdx].processingTime &&
                     availableHeap[i].index < availableHeap[minIdx].index)) {
                    minIdx = i;
                }
            }
            
            // Process the task
            result[resultCount++] = availableHeap[minIdx].index;
            currentTime += availableHeap[minIdx].processingTime;
            
            // Remove from heap
            availableHeap[minIdx] = availableHeap[heapSize - 1];
            heapSize--;
        } else {
            // No tasks available, jump to next enqueue time
            currentTime = sortedTasks[taskIdx].enqueueTime;
        }
    }
    
    free(sortedTasks);
    free(availableHeap);
    *returnSize = resultCount;
    return result;
}

int main() {
    // Simplified parsing for this example
    int tasks[3][2] = {{1,2}, {2,4}, {3,2}};
    int* taskPtrs[3] = {tasks[0], tasks[1], tasks[2]};
    int returnSize;
    
    int* result = solution(taskPtrs, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), and each task is pushed/popped from heap once (n operations × log n each)

⚡ Linearithmic

Space Complexity

O(n)

Priority queue stores up to n tasks, plus arrays for sorting and results

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~25 min Avg. Time

987 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort by Enqueue Time + Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler