销售利润最大化

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

难度: Medium

给你一个整数 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

Submission

运行时间: 203 ms

内存: 40.9 MB

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        end_dict = {}
        for start, end, gold in offers:
            if end not in end_dict:
                end_dict[end] = []
            end_dict[end].append([start, gold])
        f = [0] * (n + 1)
        for i in range(n):
            f[i+1] = f[i]
            for tmp in end_dict.get(i, []):
                f[i+1] = max(f[i+1], f[tmp[0]]+tmp[1])
        return f[n]

Explain

本题的解法采用了动态规划的思路。定义 f[i] 为考虑到第 i-1 所房屋时能获得的最大收益。对于每个结尾为 i 的要约，我们在动态规划数组中更新 f[i+1] 为 max(f[i+1], f[start] + gold)，其中 start 和 gold 是当前要约的起始房屋和提供的金币数。这样，我们不断更新在每个位置可能达到的最大收益，考虑的是接受当前要约与不接受当前要约的情况。最终，f[n] 存储的是考虑整个房屋数组时的最大收益。

时间复杂度: O(n + m)

空间复杂度: O(n + m)

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        # 创建一个字典，将每个要约按照结束编号分组
        end_dict = {}
        for start, end, gold in offers:
            if end not in end_dict:
                end_dict[end] = []
            end_dict[end].append([start, gold])
        # 动态规划数组，初始化为0
        f = [0] * (n + 1)
        for i in range(n):
            # 默认不接受新的要约，收益与前一房屋相同
            f[i+1] = f[i]
            # 检查以 i 结束的所有要约，更新最大收益
            for tmp in end_dict.get(i, []):
                f[i+1] = max(f[i+1], f[tmp[0]] + tmp[1])
        # 返回最大收益
        return f[n]

Explore

动态规划数组 f[i] 初始化为0是因为在没有任何要约的情况下，任何房屋的最大收益应为0。这个初始化也确保了算法的正确性，因为它代表着从0个房屋开始，没有任何收益的基础状态。数组 f[i] 中的每个值都代表了考虑到第 i-1 个房屋时的最大收益，因此 f[0] 表示没有房屋可考虑时的收益，自然是0。

在字典 end_dict 中按照结束编号 end 来分组要约，是为了方便在动态规划过程中快速查找所有在特定房屋编号结束的要约。这样可以直接在更新 f[i+1] 的值时，检查所有在房屋 i 结束的要约，从而决定是否接受这些要约以及如何更新收益。这种分组方式提高了算法的效率，使得每次更新只需考虑相关的要约，而不必每次都遍历所有要约。

如果对于某个房屋编号 i 没有任何要约结束，那么在动态规划中，f[i+1] 将简单地被更新为 f[i] 的值。这表示在房屋编号 i 处没有接受新的要约，因此最大收益保持与前一个房屋 i-1 相同。这样的更新确保了如果没有更好的选择（即没有新的要约或新的要约不如当前收益），我们保持现有的最大收益。

如果存在多个要约同时结束在同一房屋 i，动态规划中的实现会检查每一个要约，并尝试更新 f[i+1] 的值。具体来说，对于每个要约，我们会比较接受该要约的收益（即 f[要约的起始房屋] 加上该要约提供的金币数）与当前 f[i+1] 的值，选择两者中的最大值作为新的 f[i+1]。这意味着 f[i+1] 的最终值将是所有可能要约组合中可能获得的最大收益。