题目描述
给你一个整数 n
表示数轴上的房屋数量,编号从 0
到 n - 1
。
另给你一个二维整数数组 offers
,其中 offers[i] = [start_i, end_i, gold_i]
表示第 i
个买家想要以 gold_i
枚金币的价格购买从 start_i
到 end_i
的所有房屋。
作为一名销售,你需要有策略地选择并销售房屋使自己的收入最大化。
返回你可以赚取的金币的最大数目。
注意 同一所房屋不能卖给不同的买家,并且允许保留一些房屋不进行出售。
样例
输入: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 枚金币。
输入: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^5
1 <= offers.length <= 10^5
offers[i].length == 3
0 <= start_i <= end_i <= n - 1
1 <= gold_i <= 10^3
算法
(动态规划) $O(n \log n)$
- 设状态 $f(i)$ 表示遍历了 $[1, i]$ 的房屋后,可以赚取的金币的最大数目。预处理每个位置上,以这个位置为终点的 $offer$ 的下标。注意 $i$ 的有效下标范围是 $[1, n]$
- 初始时 $f(0) = 0$,其余待定。
- 转移时,可以转移 $f(i) = f(i - 1)$,表示不出售第 $i$ 个房屋。接着枚举以 $i$ 为终点的 $offer(x)$,转移 $f(i) = \max(f(i), f(offer(x, 0) - 1) + offer(x, 1))$。(代码中无需对 $offer(x, 0)$ 进行减一,因为给定的位置下标范围是从 $0$ 开始的。)
- 最终答案为 $f(n)$。
时间复杂度
- 预处理的时间复杂度为 $O(n)$,状态数为 $O(n)$,总的转移数为 $O(n)$,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储预处理数组和动态规划的状态。
C++ 代码
class Solution {
public:
int maximizeTheProfit(int n, vector<vector<int>>& offers) {
vector<vector<int>> p(n + 1);
for (int i = 0; i < offers.size(); i++)
p[offers[i][1] + 1].push_back(i);
const int m = offers.size();
vector<int> f(n + 1);
f[0] = 0;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1];
for (int x : p[i])
f[i] = max(f[i], f[offers[x][0]] + offers[x][2]);
}
return f[n];
}
};