Single-Threaded CPU
Problem Description
You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimei 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.
Example 1:
Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: 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]
Explanation: 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 == n1<= n <= 105- 1 <= enqueueTimei, processingTimei <= 109
Solve it on LeetCode
Approaches
1. Basic Sorting and Iteration
Intuition:
The basic idea is to represent tasks with their indices so they can be sorted effectively by when they arrive. Once sorted, we iterate through them and maintain a current time to simulate how tasks would be processed. Whenever the CPU is idle and there are no available tasks to process at that time, the CPU should skip time to the next task.
Steps:
- Parse each task into a list that stores the processing time and original index.
- Sort the list of tasks based on enqueue time as the primary key and original index as a secondary key.
- Iterate through the list of tasks, and process each task based on current time, updating current time as tasks are processed sequentially.
- Use a list to track the order of processed tasks.
Code:
- Time Complexity: Sorting the tasks costs O(N log N), where N is the number of tasks. The iteration over tasks is O(N).
- Space Complexity: O(N) is used to store the tasks and the processing order.
2. Optimized Priority Queue
Intuition:
Rather than iterating over tasks and moving time sequentially, leveraging a priority queue can optimize task processing based on the shortest processing time. This approach directly jumps to the next available task time by using a priority queue which also handles tasks with identical processing times by their original indices.
Steps:
- Store the tasks with their indices, similar to the previous approach.
- Sort the tasks based on enqueue times.
- Use a priority queue that sorts tasks first by processing time, and then by original index.
- Iterate over tasks, but using the priority queue to decide processing order.
- As before, track the order of processed tasks.
Code:
- Time Complexity: The main operations are sorting and priority queue operations, both handle N tasks, leading to O(N log N) complexity.
- Space Complexity: O(N) for storing tasks and queues.