Leetcode: 1235. Maximum Profit in Job Scheduling

Mistake: Overcomplicated solution. Tried to save memory by keeping
Can we pre-process the input in a way to make easy to solve the problem? Sort the jobs by start time. How could we find the optimal interval knowing a tiny part of it? If the job is part of the solution, it means that you can only extend it after the job's end. To find the next job, we can search for the job that starts on that time with a Binary Search. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

from typing import List
from bisect import bisect_left


class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        N = len(startTime)
        s = []
        e = []
        p = []
        for a, b, c in sorted(zip(startTime, endTime, profit)):
            s.append(a)
            e.append(b)
            p.append(c)

        dp = [0] * (N + 1)
        for i in range(N - 1, -1, -1):
            dp[i] = max(dp[i + 1], p[i] + dp[bisect_left(s, e[i], lo=i + 1)])

        return dp[0]


assert Solution().jobScheduling([1, 2, 3, 3], [3, 4, 5, 6], [50, 10, 40, 70]) == 120
assert (
    Solution().jobScheduling([1, 2, 3, 4, 6], [3, 5, 10, 6, 9], [20, 20, 100, 70, 60])
    == 150
)
assert Solution().jobScheduling([1, 1, 1], [2, 3, 4], [5, 6, 4]) == 6