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 的房屋卖给第 3 个买家，获得 2 枚金币。
可以证明我们最多只能获得 3 枚金币。

示例 2：

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

提示：

  • 1 <= n <= 10^5
  • 1 <= offers.length <= 10^5
  • offers[i].length == 3
  • 0 <= starti <= endi <= n - 1
  • 1 <= goldi <= 10^3

解题思路

这是一个经典的区间调度问题，可以用动态规划来解决。

核心思路：

  1. 预处理阶段：将报价按结束位置排序，并按位置分组，便于后续查找
  2. 动态规划：定义 dp[i] 表示在位置 [0, i] 范围内能获得的最大收益
  3. 状态转移：对于位置 i，我们有两种选择：
    • 不在位置 i 结束任何交易：dp[i] = dp[i-1]
    • 在位置 i 结束某个交易：枚举所有在位置 i 结束的报价，选择最优方案

关键优化点：

  • 使用哈希表将报价按结束位置分组，避免每次都遍历所有报价
  • 对于在位置 i 结束的每个报价 [start, end, gold]，收益为 dp[start-1] + gold
  • 最终答案为 dp[n-1]

时间复杂度主要来自于遍历所有位置和所有报价，空间复杂度为存储 DP 数组和哈希表的开销。

推荐解法：基于位置的动态规划，通过预处理分组优化查找效率。

代码实现

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        // 按结束位置分组
        unordered_map<int, vector<pair<int, int>>> groups;
        for (auto& offer : offers) {
            groups[offer[1]].emplace_back(offer[0], offer[2]);
        }
        
        vector<int> dp(n, 0);
        
        for (int i = 0; i < n; i++) {
            // 不在位置i结束任何交易
            dp[i] = (i > 0) ? dp[i-1] : 0;
            
            // 在位置i结束交易
            if (groups.count(i)) {
                for (auto& [start, gold] : groups[i]) {
                    int prev = (start > 0) ? dp[start-1] : 0;
                    dp[i] = max(dp[i], prev + gold);
                }
            }
        }
        
        return dp[n-1];
    }
};

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        from collections import defaultdict
        
        # 按结束位置分组
        groups = defaultdict(list)
        for start, end, gold in offers:
            groups[end].append((start, gold))
        
        dp = [0] * n
        
        for i in range(n):
            # 不在位置i结束任何交易
            dp[i] = dp[i-1] if i > 0 else 0
            
            # 在位置i结束交易
            if i in groups:
                for start, gold in groups[i]:
                    prev = dp[start-1] if start > 0 else 0
                    dp[i] = max(dp[i], prev + gold)
        
        return dp[n-1]

public class Solution {
    public int MaximizeTheProfit(int n, IList<IList<int>> offers) {
        // 按结束位置分组
        var groups = new Dictionary<int, List<(int start, int gold)>>();
        foreach (var offer in offers) {
            int start = offer[0], end = offer[1], gold = offer[2];
            if (!groups.ContainsKey(end)) {
                groups[end] = new List<(int, int)>();
            }
            groups[end].Add((start, gold));
        }
        
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            // 不在位置i结束任何交易
            dp[i] = (i > 0) ? dp[i-1] : 0;
            
            // 在位置i结束交易
            if (groups.ContainsKey(i)) {
                foreach (var (start, gold) in groups[i]) {
                    int prev = (start > 0) ? dp[start-1] : 0;
                    dp[i] = Math.Max(dp[i], prev + gold);
                }
            }
        }
        
        return dp[n-1];
    }
}

/**
 * @param {number} n
 * @param {number[][]} offers
 * @return {number}
 */
var maximizeTheProfit = function(n, offers) {
    // 按结束位置分组
    const groups = new Map();
    for (const [start, end, gold] of offers) {
        if (!groups.has(end)) {
            groups.set(end, []);
        }
        groups.get(end).push([start, gold]);
    }
    
    const dp = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        // 不在位置i结束任何交易
        dp[i] = i > 0 ? dp[i-1] : 0;
        
        // 在位置i结束交易
        if (groups.has(i)) {
            for (const [start, gold] of groups.get(i)) {
                const prev = start > 0 ? dp[start-1] : 0;
                dp[i] = Math.max(dp[i], prev + gold);
            }
        }
    }
    
    return dp[n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n + m)，其中 n 是房屋数量，m 是报价数量
空间复杂度O(n + m)，用于存储 DP 数组和分组哈希表