class Solution {
public:
int maximizeTheProfit(int n, vector<vector<int>>& offers) {
}
};
7006. 销售利润最大化
给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。
另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。
作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。
返回你可以赚取的金币的最大数目。
注意 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。
示例 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 <= 1051 <= offers.length <= 105offers[i].length == 30 <= starti <= endi <= n - 11 <= goldi <= 103原站题解
python3 解法, 执行用时: 368 ms, 内存消耗: 63.9 MB, 提交时间: 2023-08-21 10:20:44
'''
线性dp
'''
class Solution:
def maximizeTheProfit(self, n: int, s: List[List[int]]) -> int:
f = [0] * (n + 1)
s.sort(key = lambda x: x[1])
i = 0
for a, b, c in s:
while i <= b:
f[i + 1] = f[i]
i += 1
f[b + 1] = max(f[b + 1], f[a] + c)
return max(f)
javascript 解法, 执行用时: 340 ms, 内存消耗: 83.5 MB, 提交时间: 2023-08-21 10:20:04
/**
* @param {number} n
* @param {number[][]} offers
* @return {number}
*/
var maximizeTheProfit = function(n, offers) {
let groups = Array.from({length: n}, () => []);
for (let [s, e, cost] of offers) {
groups[e].push([s, cost]);
}
let dp = new Array(n + 1).fill(0);
for (let e = 0; e < n; e++) {
dp[e + 1] = dp[e];
for (let [s, cost] of groups[e]) {
dp[e + 1] = Math.max(dp[e + 1], dp[s] + cost);
}
}
return dp[n];
};
golang 解法, 执行用时: 200 ms, 内存消耗: 25.4 MB, 提交时间: 2023-08-21 10:19:50
func maximizeTheProfit(n int, offers [][]int) int {
type pair struct{ start, gold int }
groups := make([][]pair, n)
for _, offer := range offers {
start, end, gold := offer[0], offer[1], offer[2]
groups[end] = append(groups[end], pair{start, gold})
}
f := make([]int, n+1)
for end, g := range groups {
f[end+1] = f[end]
for _, p := range g {
f[end+1] = max(f[end+1], f[p.start]+p.gold)
}
}
return f[n]
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 368 ms, 内存消耗: 132 MB, 提交时间: 2023-08-21 10:19:15
class Solution {
public:
int maximizeTheProfit(int n, vector<vector<int>> &offers) {
vector<vector<pair<int, int>>> groups(n);
for (auto &offer: offers)
groups[offer[1]].emplace_back(offer[0], offer[2]);
vector<int> f(n + 1);
for (int end = 0; end < n; end++) {
f[end + 1] = f[end];
for (auto &[start, gold]: groups[end])
f[end + 1] = max(f[end + 1], f[start] + gold);
}
return f[n];
}
};
java 解法, 执行用时: 28 ms, 内存消耗: 113.5 MB, 提交时间: 2023-08-21 10:19:01
class Solution {
public int maximizeTheProfit(int n, List<List<Integer>> offers) {
List<int[]>[] groups = new ArrayList[n];
Arrays.setAll(groups, e -> new ArrayList<>());
for (var offer : offers)
groups[offer.get(1)].add(new int[]{offer.get(0), offer.get(2)});
var f = new int[n + 1];
for (int end = 0; end < n; end++) {
f[end + 1] = f[end];
for (var p : groups[end])
f[end + 1] = Math.max(f[end + 1], f[p[0]] + p[1]);
}
return f[n];
}
}
python3 解法, 执行用时: 300 ms, 内存消耗: 63.8 MB, 提交时间: 2023-08-21 10:17:57
'''
线性dp
定义 f[i+1] 表示销售编号不超过 i 的房屋的最大盈利。
考虑编号为 i 的房屋卖或不卖：
不卖，有 f[i+1]=f[i]。
卖，那么遍历所有 endj=i 的购买请求，有 f[i+1]=max(f[startj]+goldj。
为了方便遍历，可以先把所有 end 相同的数据用哈希表归类。
两种情况取最大值。
初始值 f[0]=0，最终答案为 f[n]。
'''
class Solution:
def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
groups = [[] for _ in range(n)]
for start, end, gold in offers:
groups[end].append((start, gold))
f = [0] * (n + 1)
for end, g in enumerate(groups):
f[end + 1] = f[end]
for start, gold in g:
f[end + 1] = max(f[end + 1], f[start] + gold)
return f[n]