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:
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 <= 1051 <= enqueueTimei, processingTimei <= 109This approach involves using a priority queue (or min-heap) to efficiently select the task with the shortest processing time. We will first sort the tasks based on their enqueue time. At each step, we'll enqueue tasks that are available and select the task with the shortest processing time for execution using the priority queue. This ensures optimal selection and execution of tasks, minimizing wait times.
The function starts by sorting tasks with indices by their enqueue time, then iteratively adds tasks to a heap that are available at the current time. It processes tasks based on the heap, which optimizes the selection of the shortest available task, ensuring tasks are processed efficiently.
JavaScript
Time Complexity: O(n log n) due to sorting and heap operations. Space Complexity: O(n) for storing tasks and heap.
This approach uses a structure like TreeMap (or Multimap) that supports ordering key-value pairs. It allows us to keep the tasks ordered by enqueue times and quickly find tasks that should start processing.
This Java solution uses a priority queue to keep track of available tasks by shortest processing time. It simulates task execution using an index-based list to ensure tasks are queried efficiently.
C++
Time Complexity: O(n log n) because of sorting and the priority queue operations. Space Complexity: O(n) for storage.
| Approach | Complexity |
|---|---|
| Using Priority Queue | Time Complexity: O(n log n) due to sorting and heap operations. Space Complexity: O(n) for storing tasks and heap. |
| Instead of Sorting, Use a Multimap (or TreeMap) | Time Complexity: O(n log n) because of sorting and the priority queue operations. Space Complexity: O(n) for storage. |
Single-Threaded CPU - Priority Queue - Leetcode 1834 - Python • NeetCode • 27,507 views views
Watch 9 more video solutions →Practice Single-Threaded CPU with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor