Tags:

2830. Maximize the Profit as the Salesman

Same as 1235

Time complexity(m log m)

Backtrack

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        
        lens = len(offers)
        offers.sort()
        
        start = [offers[i][0] for i in range(lens)]
        
        @cache
        def backtrack(i):
            if i == lens:
                return 0
            
            res = 0

            c = bisect.bisect_left(start, offers[i][1] + 1)
            
            res = max(res, offers[i][2] + backtrack(c))
            res = max(res, backtrack(i+1))
            
            return res
            
        return backtrack(0)

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        
        lens = len(offers)

        offers.sort(key=lambda x: x[1])
        end = [-1]
        dp = [0] * (lens + 1)

        offers = [0] + offers

        res = 0

        for i in range(1, lens+1):
            idx = bisect.bisect_left(end, offers[i][0])
            dp[i] = max(dp[i-1], offers[i][2] + dp[idx - 1])
            end.append(offers[i][1])
            res = max(res, dp[i])

        return res

O(n + m)

Link

Kind of Knapsack solution, if time interval < 10^5 , can try this

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        dp = [0] * (n + 1)
        m = [[] for _ in range(n)]
        for s,e,g in offers:
            m[e].append([s,g])

        for e in range(1, n + 1):
            dp[e] = dp[e - 1]
            for s, g in m[e - 1]:
                dp[e] = max(dp[e], dp[s] + g)
        return dp[-1]