销售利润最大化

You are given an integer n representing the number of houses on a number line, numbered from 0 to n - 1.

Additionally, you are given a 2D integer array offers where offers[i] = [starti, endi, goldi], indicating that ith buyer wants to buy all the houses from starti to endi for goldi amount of gold.

As a salesman, your goal is to maximize your earnings by strategically selecting and selling houses to buyers.

Return the maximum amount of gold you can earn.

Note that different buyers can't buy the same house, and some houses may remain unsold.

 

Example 1:

Input: n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
Output: 3
Explanation: There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
We sell houses in the range [0,0] to 1st buyer for 1 gold and houses in the range [1,3] to 3rd buyer for 2 golds.
It can be proven that 3 is the maximum amount of gold we can achieve.

Example 2:

Input: n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
Output: 10
Explanation: There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
We sell houses in the range [0,2] to 2nd buyer for 10 golds.
It can be proven that 10 is the maximum amount of gold we can achieve.

 

Constraints:

• 1 <= n <= 105
• 1 <= offers.length <= 105
• offers[i].length == 3
• 0 <= starti <= endi <= n - 1
• 1 <= goldi <= 103

/*
 * 思路：
 * 1. 使用Java Stream API对offers进行排序。
 * 2. 使用数组dp存储动态规划的结果。
 * 3. 使用Stream进行处理。
 */
import java.util.Arrays;

public class MaxGoldStream {
    public int maximizeGold(int n, int[][] offers) {
        Arrays.sort(offers, (a, b) -> Integer.compare(a[1], b[1])); // 按结束时间排序
        int[] dp = new int[n + 1];
        Arrays.stream(offers).forEach(offer -> {
            int start = offer[0], end = offer[1], gold = offer[2];
            dp[end + 1] = Math.max(dp[end + 1], dp[start] + gold);
            dp[end + 1] = Math.max(dp[end + 1], dp[end]);
        });
        return dp[n];
    }
}

本题的解法采用了动态规划的思路。定义 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)