Link: https://leetcode.com/problems/maximize-the-profit-as-the-salesman/description/
## 思路
We can sort by end, but we can also use bucket sort

Firstly we itearate offers,
and arange offers in a list ```m```,
where ```m[end]``` is the list of offers ending at end.

Secondly we go through end from ```1``` to ```n```,
For each end,
we initialize ```dp[end]=dp[end - 1]```,
since we can remain the endth house.
Then we check each offer ending at end,
we update ```dp[end] = max(dp[end], dp[start] + gold)```

Finally we return ```dp[n]``` as result.
## Code
$O(m+n)$

class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
dp = [0]*(n+1)
endMap = [[] for _ in range(n)]
for start, end, gold in offers:
endMap[end].append([start, gold])
for end in range(1, n+1):
dp[end] = dp[end-1]
for start, gold in endMap[end-1]:
dp[end] = max(dp[end], dp[start]+gold)
return dp[n]