Problem statement

https://binarysearch.com/problems/A-Student/

Solution

Similar to Leetcode 0630. Course Schedule III, but here instead of removing the course with the smallest duration from heap, we remove the course with smallest credits.

Complexity

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

Code

class Solution:
    def solve(self, deadlines, credits):
        heap = []
        for deadline, val in sorted(zip(deadlines, credits)):
            heappush(heap, val)
            if len(heap) > deadline + 1:
                heappop(heap)
        return sum(heap)