Problem statement

https://leetcode.com/problems/single-threaded-cpu/

Solution

In this problem we need to simulate process with heap, where we keep in heap avaliable tasks. First, we add all possible candidates to heap. Then if heap is not empty, we extract candidate and increase time and add it to answer. If heap is empty, we jump to next time tasks[i][0]

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def getOrder(self, tasks):
        tasks = sorted([(t, s, i) for i, (t, s) in enumerate(tasks)])
        res, heap, i, n, time = [], [], 0, len(tasks), tasks[0][0]
        
        while len(res) < n:
            while i < n and tasks[i][0] <= time:
                heappush(heap, (tasks[i][1:]))
                i += 1
            if heap:
                dur, idx = heappop(heap)
                time += dur
                res.append(idx)
            elif i < n:
                time = tasks[i][0]
        return res