Problem statement

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

Solution

Similar to Leetcode 0630. Course Schedule III: the key idea is to sort data by ends. Then we use dp(i, time), where it is the maximum score we can get when we use [i, n-1] courses and reached time time. Then we can have two options: to take course or not.

Complexity

It is O(n * m), where n = len(arr) and m = max(ends). Notice that it can be made as O(n^2) if we use coordinate compression, however given constraints it is not necessary.

Code

class Solution:
    def solve(self, ends, credits, durs):
        arr = sorted([e, c, d] for e, c, d in zip(ends, credits, durs))

        @lru_cache(None)
        def dp(i, time):
            if i == len(arr): return 0
            ans = dp(i + 1, time)
            if time + arr[i][2] <= arr[i][0]:
                ans = max(ans, dp(i + 1, time + arr[i][2]) + arr[i][1])
            return ans 

        return dp(0, -1)