编程算法面试常考题答案汇总
Leetcode 2830 - Maximize the Profit as the Salesman
Coding Interview Question: Maximize the Profit as the Salesman [Leetcode 2830]
You are given an integer n representing the number of houses on a number line, numbered from 0 to n - 1.
Additionally, you are given a 2D integer array offers where offers[i] = [starti, endi, goldi], indicating that ith buyer wants to buy all the houses from starti to endi for goldi amount of gold.
As a salesman, your goal is to maximize your earnings by strategically selecting and selling houses to buyers.
Return the maximum amount of gold you can earn.
Note that different buyers can't buy the same house, and some houses may remain unsold.
Solution
# 本代码来自 Techie科技求职，由 Techie Learning,Inc 原创
# - Techielearning.com 是来自硅谷的科技职业发展平台。
# - 本代码所属课程：<< Techie编程算法集训营 >>
# - 12周56+课时精品内容，精讲软件工程师编程算法面试核心知识体系。
# - 120道面试真题详解，27类常考题型剖析，1对1面试辅导与专业答疑。
# - 官方网站：https://www.techielearning.com/
# - 版权所有，禁止转发和分享
# Solution 1: Top-down implementation
def upper_bound(offers, i, v):
l, r = i, len(offers)
while l < r:
m = (l + r) / 2
if offers[m][0] > v:
r = m
else:
l = m + 1
return l
class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
offers.sort()
@lru_cache(None)
def f(i):
if i == len(offers):
return 0
return max(f(i + 1), f(upper_bound(offers, i, offers[i][1])) + offers[i][2])
return f(0)
# Solution 2: Bottom-up implementation
def upper_bound(offers, i, v):
l, r = i, len(offers)
while l < r:
m = (l + r) / 2
if offers[m][0] > v:
r = m
else:
l = m + 1
return l
class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
offers.sort()
dp = [0] * (len(offers) + 1)
for i in reversed(range(len(offers))):
dp[i] = max(dp[i + 1], dp[upper_bound(offers, i, offers[i][1])] + offers[i][2])
return dp[0]
如果大家对题目代码有任何问题，欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信。期待与同学们继续交流！
