Untitled

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        offers = sorted(offers, key=lambda x: x[0])

        def binary_search(low, high, target):
            while low <= high:
                mid = (low + high) // 2
                if offers[mid][0] > target:
                    high = mid - 1
                else:
                    low = mid + 1
            return low
        
        @cache
        def helper(index):
            if index >= len(offers):
                return 0

            curr_start, curr_end, curr_gold = offers[index]

            reject_offer = helper(index+1)

            next_valid_offer = binary_search(index+1, len(offers)-1, curr_end)
            accept_offer = helper(next_valid_offer) + curr_gold
            
            return max(reject_offer, accept_offer)

        return helper(0)