Question

2830. 销售利润最大化

English Version

题目描述

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

解法

方法一：排序 + 二分查找 + 动态规划

我们将所有的购买要约按照 $end$ 从小到大排序，然后使用动态规划求解。

定义 $f[i]$ 表示前 $i$ 个购买要约中，我们可以获得的最大金币数。答案即为 $f[n]$。

对于 $f[i]$，我们可以选择不卖出第 $i$ 个购买要约，此时 $f[i] = f[i - 1]$；也可以选择卖出第 $i$ 个购买要约，此时 $f[i] = f[j] + gold_i$，其中 $j$ 是满足 $end_j \leq start_i$ 的最大下标。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是购买要约的数量。

class Solution:
  def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
    offers.sort(key=lambda x: x[1])
    f = [0] * (len(offers) + 1)
    g = [x[1] for x in offers]
    for i, (s, _, v) in enumerate(offers, 1):
      j = bisect_left(g, s)
      f[i] = max(f[i - 1], f[j] + v)
    return f[-1]

class Solution {
  public int maximizeTheProfit(int n, List<List<Integer>> offers) {
    offers.sort((a, b) -> a.get(1) - b.get(1));
    n = offers.size();
    int[] f = new int[n + 1];
    int[] g = new int[n];
    for (int i = 0; i < n; ++i) {
      g[i] = offers.get(i).get(1);
    }
    for (int i = 1; i <= n; ++i) {
      var o = offers.get(i - 1);
      int j = search(g, o.get(0));
      f[i] = Math.max(f[i - 1], f[j] + o.get(2));
    }
    return f[n];
  }

  private int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int maximizeTheProfit(int n, vector<vector<int>>& offers) {
    sort(offers.begin(), offers.end(), [](const vector<int>& a, const vector<int>& b) {
      return a[1] < b[1];
    });
    n = offers.size();
    vector<int> f(n + 1);
    vector<int> g;
    for (auto& o : offers) {
      g.push_back(o[1]);
    }
    for (int i = 1; i <= n; ++i) {
      auto o = offers[i - 1];
      int j = lower_bound(g.begin(), g.end(), o[0]) - g.begin();
      f[i] = max(f[i - 1], f[j] + o[2]);
    }
    return f[n];
  }
};

func maximizeTheProfit(n int, offers [][]int) int {
  sort.Slice(offers, func(i, j int) bool { return offers[i][1] < offers[j][1] })
  n = len(offers)
  f := make([]int, n+1)
  g := []int{}
  for _, o := range offers {
    g = append(g, o[1])
  }
  for i := 1; i <= n; i++ {
    j := sort.SearchInts(g, offers[i-1][0])
    f[i] = max(f[i-1], f[j]+offers[i-1][2])
  }
  return f[n]
}

function maximizeTheProfit(n: number, offers: number[][]): number {
  offers.sort((a, b) => a[1] - b[1]);
  n = offers.length;
  const f: number[] = Array(n + 1).fill(0);
  const g = offers.map(x => x[1]);
  const search = (x: number) => {
    let l = 0;
    let r = n;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (g[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (let i = 1; i <= n; ++i) {
    const j = search(offers[i - 1][0]);
    f[i] = Math.max(f[i - 1], f[j] + offers[i - 1][2]);
  }
  return f[n];
}