Problem statement

https://binarysearch.com/problems/CPU-Scheduling/

Solution

Equal to Leetcode 1834. Single-Threaded CPU.

Complexity

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

Code

class Solution:
    def solve(self, tasks):
        tasks = sorted([(t, s, i) for i, t, s in 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