What is the main strategy to maximize profit in Maximize the Profit as the Salesman?

Use array scanning combined with dynamic programming and hash lookups to select non-overlapping offers with the highest cumulative gold.

Why do we need to sort offers by end index?

Sorting ensures when considering an offer, all prior compatible offers are already evaluated, simplifying dynamic programming updates.

Can overlapping offers ever be selected?

No, overlapping offers violate the house sale constraints, and including them would reduce the total achievable gold.

How does the hash table help in the DP solution?

It maps end indices to maximum profits, allowing constant-time lookups of compatible previous offers, improving efficiency over linear searches.

What common mistakes should I avoid in this problem?

Do not forget to sort offers, avoid selecting overlapping offers, and ensure DP updates consider the best prior profits for non-overlapping sequences.

#2830

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

销售利润最大化

给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。另给你一个二维整数数组 offers ，其中 offers[i] = [start i , end i , gold i ] 表示第 i 个买家想要以 gold i 枚金币的价格购买从 start i 到 end i 的所有房屋…

数组哈希表二分查找动态规划排序

题目描述

给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。

另给你一个二维整数数组 offers ，其中 offers[i] = [start_i, end_i, gold_i] 表示第 i 个买家想要以 gold_i 枚金币的价格购买从 start_i 到 end_i 的所有房屋。

作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。

返回你可以赚取的金币的最大数目。

注意同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。

示例 1：

输入：n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
输出：3
解释：
有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家，并将位于 [1,3] 范围内的房屋以 2 金币的价格出售给第 3 位买家。
可以证明我们最多只能获得 3 枚金币。

示例 2：

输入：n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
输出：10
解释：有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,2] 范围内的房屋以 10 金币的价格出售给第 2 位买家。
可以证明我们最多只能获得 10 枚金币。

提示：

1 <= n <= 10⁵
1 <= offers.length <= 10⁵
offers[i].length == 3
0 <= start_i <= end_i <= n - 1
1 <= gold_i <= 10³

lightbulb

解题思路

方法一：排序 + 二分查找 + 动态规划

我们将所有的购买要约按照 $end$ 从小到大排序，然后使用动态规划求解。

定义 $f[i]$ 表示前 $i$ 个购买要约中，我们可以获得的最大金币数。答案即为 $f[n]$ 。

对于 $f[i]$ ，我们可以选择不卖出第 $i$ 个购买要约，此时 $f[i] = f[i - 1]$ ；也可以选择卖出第 $i$ 个购买要约，此时 $f[i] = f[j] + gold_i$ ，其中 $j$ 是满足 $end_j \leq start_i$ 的最大下标。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是购买要约的数量。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        offers.sort(key=lambda x: x[1])
        f = [0] * (len(offers) + 1)
        g = [x[1] for x in offers]
        for i, (s, _, v) in enumerate(offers, 1):
            j = bisect_left(g, s)
            f[i] = max(f[i - 1], f[j] + v)
        return f[-1]

speed

复杂度分析

指标	值
时间	complexity is dominated by sorting offers O(m log m) where m is the number of offers, plus linear DP iteration O(m), yielding O(m log m) total. Space complexity is O(n) for the DP array or O(m) if using a hash map to store intermediate maximum profits.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for overlapping ranges; naive selection leads to suboptimal profit.
question_mark
Consider how dynamic programming can combine prior optimal selections efficiently.
question_mark
Using a hash map for end indices can significantly reduce lookup time.

warning

常见陷阱

外企场景

error
Forgetting to sort offers by end index before DP calculation.
error
Including overlapping offers that invalidate prior selections.
error
Ignoring hash table optimizations, leading to slower O(n*m) checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow offers with partial overlaps and maximize profit using interval scheduling with weights.
arrow_right_alt
Restrict gold amounts to multiples of a constant and compute maximum using modular arithmetic DP.
arrow_right_alt
Add a cost for skipping houses and maximize net profit including both sales and skip penalties.

help

常见问题

外企场景

继续练习

#2713 矩阵中严格递增的单元格数 #2501 数组中最长的方波 #3186 施咒的最大总伤害