1235

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

        jobs = [(startTime[i], endTime[i], profit[i]) for i in range(len(profit))]
        jobs.sort(key=lambda x: x[1])

        memo = defaultdict(int)

        e_prev = 0
        for i, (s, e, p) in enumerate(jobs):
            memo[e] = max(memo[e], p)
            memo[e] = max(memo[e], memo[e_prev])
            e_prev = e

            if jobs[0][1] <= s:
                l = 0
                r = i
                while r - l > 1:
                    mid = l + (r - l) // 2
                    if jobs[mid][1] <= s:
                        l = mid
                    else:
                        r = mid

                memo[e] = max(memo[e], p + memo[jobs[l][1]])

        return memo[e]