Untitled
unknown
python
a year ago
868 B
1
Indexable
Never
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)