Single-Threaded CPU

66.1k
0

Given an array tasks, every entry tasks[index] = [enqueueTime, processingTime] describes one indexed task. The enqueue time marks the first available moment, and the processing time gives the full execution duration.

A single-threaded CPU handles at most one task at a time. An idle CPU selects the available task with the shortest processing time. Equal processing times are resolved by the smaller original index. A started task runs to completion without interruption. Return the task indices in execution order.

Example 1

Input: tasks = [[1, 2], [2, 4], [3, 2], [4, 1]]
Output: [0, 2, 3, 1]
Explanation: Task 0 runs from time 1 to 3. Tasks 1 and 2 are then available, so the shorter task 2 runs next. Task 3 has the shortest duration at time 5, leaving task 1 for the final position.

Example 2

Input: tasks = [[5, 2], [5, 2], [5, 1]]
Output: [2, 0, 1]
Explanation: The CPU remains idle until time 5. Task 2 has the shortest processing time. Tasks 0 and 1 have equal durations, so the smaller index 0 receives priority.

Brute Force Approach

The scheduling rule can be followed literally. At every free moment, a complete scan can find every unfinished task already available. The best candidate has the smallest processing time, with the original index breaking a tie.

An empty candidate set means the CPU has reached an idle gap. Moving the clock to the earliest unfinished enqueue time avoids checking every empty time unit. Repeated full scans keep the method simple, but the same task list may be inspected many times.

Algorithm

  • Begin with a completion array, an empty execution order, and time 0, so unfinished tasks and simulated time remain visible throughout the process.

  • Scan every unfinished task at each free CPU moment, because only enqueue times at or before the current time create valid candidates.

  • Keep the candidate with the smallest processing time and then the smallest index, so every selection follows both CPU priority rules.

  • Track the earliest enqueue time among unfinished tasks during the same scan, so an idle gap can be skipped without testing empty time units.

  • Move the clock to the earliest unfinished enqueue time when no candidate exists, because no task can start before the next arrival.

  • Mark a selected task as completed, append the original index, and add the full processing duration, because execution cannot be interrupted.

  • Return the recorded indices after every task finishes, because insertion order matches the complete CPU schedule.

Dry Run

Single-Threaded CPU - Brute Force Approach

Single-Threaded CPU - Brute Force Approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the CPU order through repeated scans.
vector<int> getOrder(vector<vector<int>>& tasks) {
int n = tasks.size();
vector<bool> completed(n, false);
vector<int> order;
long long currentTime = 0;
// Continue until every task enters the order.
while (order.size() < n) {
int selected = -1;
long long nextEnqueue = LLONG_MAX;
// Inspect every unfinished scheduling choice.
for (int index = 0; index < n; index++) {
// Completed tasks cannot run a second time.
if (completed[index]) {
continue;
}
// Preserve the next possible wake-up time.
nextEnqueue = min(
nextEnqueue,
(long long) tasks[index][0]
);
// Future tasks are not valid candidates yet.
if (tasks[index][0] > currentTime) {
continue;
}
// The first available task starts comparison.
if (selected == -1) {
selected = index;
continue;
}
int duration = tasks[index][1];
int bestDuration = tasks[selected][1];
// A shorter task receives higher priority.
if (duration < bestDuration) {
selected = index;
// A smaller index resolves an equal duration.
} else if (
duration == bestDuration && index < selected
) {
selected = index;
}
}
// An idle CPU waits for the next task arrival.
if (selected == -1) {
currentTime = nextEnqueue;
continue;
}
// Completion prevents another future selection.
completed[selected] = true;
// The chosen index becomes the next answer entry.
order.push_back(selected);
// Non-preemptive work consumes the full duration.
currentTime += tasks[selected][1];
}
// Recorded selection order is the CPU schedule.
return order;
}
};
// Driver code
int main() {
vector<vector<int>> tasks = {
{1, 2}, {2, 4}, {3, 2}, {4, 1}
};
Solution obj;
vector<int> answer = obj.getOrder(tasks);
cout << "[";
for (int index = 0; index < answer.size(); index++) {
cout << answer[index];
cout << (index + 1 < answer.size() ? ", " : "");
}
cout << "]" << endl;
return 0;
}

Note: The brute-force scan may fail for large task collections. Repeated full scans create quadratic work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(N2), where N is the number of tasks, because each completed task may require a constant number of full scans over the task list.

Space Complexity: O(N), because the completion array and returned execution order each store at most N entries.

Optimal Approach

The repeated scan can be removed by separating future tasks from available tasks. Sorting by enqueue time creates a single forward path through future arrivals. Every task crosses into the available group exactly once.

A min heap keeps the available group ordered by processing time and original index. The top entry always matches the CPU priority rule. An empty heap signals an idle gap, so the clock can jump straight to the next sorted enqueue time.

Algorithm

  • Attach every original index to the matching enqueue and processing times, so sorting never loses the required output identity.

  • Sort the enriched tasks by enqueue time, so one pointer can reveal arrivals in chronological order without repeated future-task scans.

  • Keep a min heap ordered by processing time and then original index, so the heap top always represents the next valid CPU choice.

  • Jump the current time to the next enqueue time whenever the heap is empty, because no available work can fill the idle interval.

  • Move every task with enqueue time at or before the current time into the heap, so the candidate set contains all legal choices.

  • Remove the heap top, append the original index, and add the processing duration, because a selected task runs without interruption.

  • Continue until the sorted list and heap are empty, then return the recorded order because every task has already finished.

Dry Run

Diagram 1
1 / 3

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the CPU order with sorting and a heap.
vector<int> getOrder(vector<vector<int>>& tasks) {
int n = tasks.size();
vector<vector<int>> orderedTasks;
// Preserve each index before sorting by arrival.
for (int index = 0; index < n; index++) {
orderedTasks.push_back({
tasks[index][0], tasks[index][1], index
});
}
// Chronological order exposes new tasks once.
sort(orderedTasks.begin(), orderedTasks.end());
priority_queue<
pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>
> available;
vector<int> order;
int pointer = 0;
long long currentTime = 0;
// Pending or available work keeps simulation active.
while (pointer < n || !available.empty()) {
// An empty heap allows a direct clock jump.
if (
available.empty() &&
currentTime < orderedTasks[pointer][0]
) {
currentTime = orderedTasks[pointer][0];
}
// Add every task ready at the current time.
while (
pointer < n &&
orderedTasks[pointer][0] <= currentTime
) {
int processingTime =
orderedTasks[pointer][1];
int originalIndex =
orderedTasks[pointer][2];
// Heap keys match duration and index priority.
available.push({
processingTime, originalIndex
});
pointer++;
}
// Heap top is the required available task.
pair<int, int> selected = available.top();
available.pop();
// The chosen index becomes the next answer entry.
order.push_back(selected.second);
// Non-preemptive work consumes the full duration.
currentTime += selected.first;
}
// Recorded heap selections form the CPU schedule.
return order;
}
};
// Driver code
int main() {
vector<vector<int>> tasks = {
{1, 2}, {2, 4}, {3, 2}, {4, 1}
};
Solution obj;
vector<int> answer = obj.getOrder(tasks);
cout << "[";
for (int index = 0; index < answer.size(); index++) {
cout << answer[index];
cout << (index + 1 < answer.size() ? ", " : "");
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of tasks, because sorting takes O(N log N) and each task enters and leaves the min-heap once.

Space Complexity: O(N), because the task list, min-heap, and returned order each store at most N entries.

Interview follow-up Questions

No. Task execution is non-preemptive, so a started task finishes before another task can begin.

Heap

Read Similar Blogs

Heap

Merge K Sorted Linked Lists

Given an array lists containing the heads of k singly linked lists, merge every node into one linked list sorted in non-decreasing order. Every input list is already sorted in non-decreasing order....

92.2k
Heap

Introduction to Heap

Imagine an emergency room with several waiting patients. The patient needing the most urgent care is treated first, even if another patient arrived earlier. The next choice depends on...

72.8k
Heap

Meeting Rooms II

Given an array intervals , where every entry [start, end] represents one meeting, find the minimum number of conference rooms needed to hold every meeting without a scheduling conflict. An end time...

57.7k
Comments0