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 <= 10^51 <= enqueueTimei, processingTimei <= 10^9
The description was taken from https://leetcode.com/problems/single-threaded-cpu/.
#O(N(Log(N))) Time, O(N) Space
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
enqueue, processes = [], []
output = []
for i, task in enumerate(tasks):
heapq.heappush(enqueue, (task[0], task[1], i))
time = enqueue[0][0]
while enqueue or processes:
while enqueue and enqueue[0][0] <= time:
_, load, task = heapq.heappop(enqueue)
heapq.heappush(processes, (load, task))
if processes:
load, task = heapq.heappop(processes)
time += load
output.append(task)
else:
time = enqueue[0][0]
return outputAccording to the problem description, we are to prioritize tasks by their enqueue time and if there are ties in tasks then we should prioritize the task with the shortest processing time.
Since we are prioritizing tasks, we should utilize a priority queue which we will implement through a heap.
We will start by initializing a timer count and pushing each task into an enqueue heap, at which point we will continuously pop each task with an enqueue time less than or equal to the current time from that heap and place it into a processing heap. The processing heap will sort on processing time so we will be able to prioritize the tasks with the least processing time, that we know are ready to be enqueued.
We'll increment the time count by the processing time each time we pop from the processes heap, and if we run out of processes to enqueue, we will just increment the timer to the top of the enqueue heap so that we can continue.
Let's start by initializing our enqueue and processes heaps, and also our output list.
enqueue, processes = [], []
output = []
Next, for each task in the tasks list, we will push it into the enqueue heap along with its index which is its ID so that we can return the order of the tasks that were completed.
for i, task in enumerate(tasks):
heapq.heappush(enqueue, (task[0], task[1], i))
We'll start our timer to the first task to be enqueued.
time = enqueue[0][0]
Then, while we have tasks in one of our heaps, we will continue fulfilling these tasks.
while enqueue or processes:
While we still have tasks in our enqueue heap and while the top task's enqueue time is less than or equal to the current time, we will pop it and push it into the processes heap with the load, the processing time, being what the heap will sort on.
while enqueue and enqueue[0][0] <= time:
_, load, task = heapq.heappop(enqueue)
heapq.heappush(processes, (load, task))
If we have tasks in our processes heap that we can enqueue, we will pop the load and the task ID, increment the time by the load then output the task ID.
if processes:
load, task = heapq.heappop(processes)
time += load
output.append(task)
Otherwise, we will increment the time by the top of the enqueue heap so that we can enqueue the next task and keep the ball rolling.
else:
time = enqueue[0][0]
Once we have finished processing each task, we will return the order that the tasks that were processed.
return output