Leetcode 1834. Single-Threaded CPU

Problem

Leetcode 1834 - Single-Threaded CPU

Example:

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.

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.

Approach

We can sort the tasks to get organize the enqueueTime. Before we do we must append the index to each task to keep track of the index of each task.

Now our tasks should look like (enqueueTime, processTime, index) for each task.

We can then initialize some variables like time, and minHeap array.

We run a while loop until len(res) = len(tasks)

• while enqueueTime <= time and index < len(tasks)-
  • heappush(processTime, index)
  • increment index
• if our minHeap is empty
  • append tasks[index] to heap
  • time = tasks[index]’s enqueueTime
• else
  • heappop from minHeap
  • append the index to res
  • increment time by how much processTime that task took

Here is the Python code for the solution:

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        for i, task in enumerate(tasks):
            task.append(i)
        
        tasks.sort()
        res, heap = [], []
        heapq.heapify(heap)
        index, time = 0, tasks[index][0]

        while (len(res) < len(tasks)):

            while (index < len(tasks) and tasks[index][0] <= time):
                heapq.heappush(heap, (tasks[index][1], tasks[index][2]))
                index += 1
            
            if (len(heap) == 0):
                heapq.heappush(heap, (tasks[index][1], tasks[index][2]))
                time = tasks[index][0]
                index += 1
            else:
                task = heapq.heappop(heap)
                res.append(task[1])
                time += task[0]

        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n log n)$

Space Complexity: $O(n)$