Max Profit Non Overlap Intervals

"""
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.
"""

class Solution:

    def solve(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        intervals = sorted(zip(startTime, endTime, profit), key = lambda item: item[0])
        dp = [None for _ in range(len(intervals))]

        """ OLD
        for i in range(len(dp)):
            self.max_profit_from(i, dp, intervals = intervals)
        return max(dp)
        """

        start_interval_i = 0

        """ Recursive Solution
        self.max_profit_from(start_interval_i, dp, intervals = intervals)
        """
        self.dp_solution(dp, intervals = intervals)

        ans = dp[start_interval_i - 0]
        return ans

    def is_not_overlap(self, interval1: "tuple", interval2: "tuple"):
        start1, end1 = interval1
        start2, end2 = interval2
        return end1 <= start2 or end2 <= start1

    def binary_search(self,
        start_i, end_i, want_first_true: "bool",
        *, decide_func, **kwargs): # -> index | None

        if start_i > end_i:
            return None

        left_i = start_i; right_i = end_i; is_satisfy_problem = False
        while left_i <= right_i:

            # [a, b] -> a; [a, b, c] -> b
            mid_i = left_i + (right_i - left_i) // 2

            is_satisfy_problem = decide_func(mid_i, **kwargs)
            if is_satisfy_problem == want_first_true:
                right_i = mid_i - 1
            else:
                left_i = mid_i + 1

        final_i = left_i if want_first_true else left_i - 1
        return final_i if start_i <= final_i <= end_i else None

    def dp_solution(self, dp, *, intervals):
        """
        Time Complexity: O(nlogn) -- n = len(intervals)
        Space Complexity: O(n) -- n = len(intervals)
        """
        for interval_i in range(len(intervals) - 1, -1, -1):
            dp_interval_i = interval_i

            ans = dp[dp_interval_i]
            if ans is None:
                if interval_i == len(intervals) - 1: # Base
                    ans = intervals[interval_i][2]
                else:
                    next_non_overlap_index = self.binary_search(
                        interval_i + 1, len(intervals) - 1,
                        want_first_true = True,
                        decide_func = lambda mid_i: self.is_not_overlap(
                            intervals[mid_i][:2], intervals[interval_i][:2]
                        )
                    )
                    useIt_ans = intervals[interval_i][2]
                    if next_non_overlap_index is not None:
                        next_ans = dp[next_non_overlap_index]
                        useIt_ans += next_ans

                    lostIt_ans = dp[interval_i + 1]
                    ans = max(useIt_ans, lostIt_ans)

            dp[dp_interval_i] = ans
        return dp

    def max_profit_from(self, interval_i, dp, *, intervals: "list[interval]"):
        dp_interval_i = interval_i

        ans = dp[dp_interval_i]
        if ans is None:
            if interval_i == len(intervals) - 1: # Base
                ans = intervals[interval_i][2]
            else:
                """ OLD
                ans = -float('inf')
                for next_interval_i in range(interval_i + 1, len(intervals)):
                    if not self.is_not_overlap(intervals[interval_i][:2], intervals[next_interval_i][:2]):
                        continue

                    next_ans = self.max_profit_from(
                        next_interval_i, dp,
                        intervals = intervals
                    )

                    ans = max(ans, next_ans + intervals[interval_i][2])
                if ans == -float('inf'):
                    ans = intervals[interval_i][2]
                """

                next_non_overlap_index = self.binary_search(
                    interval_i + 1, len(intervals) - 1,
                    want_first_true = True,
                    decide_func = lambda mid_i: self.is_not_overlap(
                        intervals[mid_i][:2], intervals[interval_i][:2]
                    )
                )
                useIt_ans = intervals[interval_i][2]
                if next_non_overlap_index is not None:
                    next_ans = self.max_profit_from(next_non_overlap_index, dp, intervals = intervals)
                    useIt_ans += next_ans

                lostIt_ans = self.max_profit_from(interval_i + 1, dp, intervals = intervals)
                ans = max(useIt_ans, lostIt_ans)

        dp[dp_interval_i] = ans
        return ans