2830-销售利润最大化

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个整数 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 <= 105
  • 1 <= offers.length <= 105
  • offers[i].length == 3
  • 0 <= starti <= endi <= n - 1
  • 1 <= goldi <= 103

请看 视频讲解 第三题。

前置知识：动态规划入门

详见 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】

思路

定义 f[i+1] 表示销售编号不超过 i 的房屋的最大盈利。

考虑编号为 i 的房屋卖或不卖：

  • 不卖，有 f[i+1]=f[i]。
  • 卖，那么遍历所有 end}_j=i 的购买请求，有 f[i+1] = \max (f[\textit{start}_j]+\textit{gold}_j)。为了方便遍历，可以先把所有 end 相同的数据用哈希表归类。
  • 两种情况取最大值。

初始值 f[0]=0。

最终答案为 f[n]。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
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]
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 }

复杂度分析

  • 时间复杂度：\mathcal{O}(n+m)，其中 m 为 offers 的长度。
  • 空间复杂度：\mathcal{O}(n+m)。

相似题目

 Comments
On this page
2830-销售利润最大化
  1. 前置知识：动态规划入门
  2. 思路
  3. 相似题目