#1834

Medium

LeetCode Problem Workspace

Single-Threaded CPU

Simulate task processing with a single-threaded CPU by sorting and prioritizing tasks based on arrival and processing times.

array sorting heap priority queue

Problem Statement

You are given a list of tasks where each task is represented by a pair of values: enqueueTime and processingTime. The task will be available at enqueueTime and will take processingTime to finish. You are working with a single-threaded CPU that can only handle one task at a time.

The CPU starts processing tasks as soon as they are available. If multiple tasks are available at the same time, the CPU will prioritize the task with the shortest processing time. Your goal is to determine the order in which the tasks will be processed.

Examples

Example 1

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

Output: [0,2,3,1]

The events go as follows:

At time = 1, task 0 is available to process. Available tasks = {0}.
Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
At time = 2, task 1 is available to process. Available tasks = {1}.
At time = 3, task 2 is available to process. Available tasks = {1, 2}.
Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
At time = 4, task 3 is available to process. Available tasks = {1, 3}.
At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
At time = 10, the CPU finishes task 1 and becomes idle.

Example 2

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

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

The events go as follows:

At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
At time = 40, the CPU finishes task 1 and becomes idle.

Constraints

tasks.length == n
1 <= n <= 105
1 <= enqueueTimei, processingTimei <= 109

Solution Approach

Sort by Enqueue Time

Start by sorting the tasks based on their enqueueTime. This allows you to track when tasks become available and simulate the task arrival order. Sorting helps you handle tasks in the correct sequence.

Use Heap to Prioritize Tasks

Use a min-heap (priority queue) to efficiently select the task with the shortest processing time at each moment. As tasks arrive, push them into the heap, and at each step, pop the task with the shortest processing time to process next.

Simulate Task Execution

Simulate the task processing, updating the current time and checking the availability of new tasks. If the CPU becomes idle, wait for the next task or process the one available in the heap.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how tasks are sorted and processed. Sorting the tasks takes O(n log n), and managing the heap for task selection takes O(log n) for each task. Therefore, the overall time complexity is O(n log n). The space complexity is O(n) due to storing tasks and the heap.

What Interviewers Usually Probe

Look for the candidate's understanding of sorting and heap usage for task prioritization.
Watch for the candidate's ability to efficiently simulate the process while managing available tasks.
Check if the candidate efficiently handles edge cases like tasks arriving at the same time.

Common Pitfalls or Variants

Common pitfalls

Not handling idle CPU situations properly when there are no tasks to process.
Forgetting to prioritize the shortest task when multiple tasks are available.
Overcomplicating the task management instead of leveraging sorting and heap efficiently.

Follow-up variants

Modify the problem to handle a multi-threaded CPU with more than one task running simultaneously.
Change the tasks' characteristics to involve different priority schemes (e.g., prioritize by processing time or enqueue time).
Introduce task dependencies where some tasks cannot be started until others are completed.

FAQ

How do you simulate task processing in the Single-Threaded CPU problem?

By sorting the tasks by enqueueTime and using a heap to process the shortest task first, simulating the CPU's task execution.

What is the time complexity of solving the Single-Threaded CPU problem?

The time complexity is O(n log n) due to sorting the tasks and managing the heap for task selection.

How does the heap help in solving the Single-Threaded CPU problem?

The heap allows efficient prioritization of tasks with the shortest processing time, ensuring optimal task selection during CPU simulation.

What edge cases should I consider in the Single-Threaded CPU problem?

Consider edge cases like tasks arriving at the same time, tasks with equal processing times, and idle CPU situations when no tasks are available.

Can the Single-Threaded CPU problem be modified to work with multi-threaded CPUs?

Yes, the problem can be modified by allowing the CPU to process multiple tasks simultaneously, requiring a different simulation approach.

terminal

Solution

Solution 1: Sorting + Priority Queue (Min Heap)

First, we sort the tasks by `enqueueTime` in ascending order. Next, we use a priority queue (min heap) to maintain the currently executable tasks. The elements in the queue are `(processingTime, index)`, which represent the execution time and the index of the task. We also use a variable $t$ to represent the current time, initially set to $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        for i, task in enumerate(tasks):
            task.append(i)
        tasks.sort()
        ans = []
        q = []
        n = len(tasks)
        i = t = 0
        while q or i < n:
            if not q:
                t = max(t, tasks[i][0])
            while i < n and tasks[i][0] <= t:
                heappush(q, (tasks[i][1], tasks[i][2]))
                i += 1
            pt, j = heappop(q)
            ans.append(j)
            t += pt
        return ans

Continue Practicing

#1851 minimum interval to include each query #1878 get biggest three rhombus sums in a grid #1738 find kth largest xor coordinate value