题目描述

在一条数轴上有无限多个袋子，每个坐标对应一个袋子。其中一些袋子里装有硬币。

给你一个二维数组 coins，其中 coins[i] = [l_i, r_i, c_i] 表示从坐标 l_i 到 r_i 的每个袋子中都有 c_i 枚硬币。

数组 coins 中的区间互不重叠。

另给你一个整数 k。

返回通过收集连续 k 个袋子可以获得的 最多 硬币数量。

样例

输入： coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4

输出： 10

解释：

选择坐标为 [3, 4, 5, 6] 的袋子可以获得最多硬币：2 + 0 + 4 + 4 = 10。

输入： coins = [[1,10,3]], k = 2

输出： 6

解释：

选择坐标为 [1, 2] 的袋子可以获得最多硬币：3 + 3 = 6。

限制

• 1 <= coins.length <= 10^5
• 1 <= k <= 10^9
• coins[i] == [l_i, r_i, c_i]
• 1 <= l_i <= r_i <= 10^9
• 1 <= c_i <= 1000
• 给定的区间互不重叠。

算法

(贪心，滑动窗口) $O(n \log n)$

1. 注意到，最优答案一定存在于以某个区间的左端点为起点，或者以某个区间的右端点为终点的长度为 $k$ 的区间。否则，可以通过左右移动区间使得答案不会变差。
2. 为了方便处理，将两个区间中间间隔的部分用一段价值为 $0$ 的区间填充。
3. 将所有区间从小到大排序，使用滑动窗口求解最大的价值。即每次判断是将起点移动到下一个区间的左端点，还是将终点移动到当前区间的右端点。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 排序后，遍历所有区间一次。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序的系统栈和新区间。

C++ 代码

#define LL long long

class Solution {
public:
    LL maximumCoins(vector<vector<int>>& coins, int k) {
        int n = coins.size();

        sort(coins.begin(), coins.end());

        vector<vector<int>> new_coins;
        for (int i = 0; i < n - 1; i++) {
            new_coins.push_back({coins[i][0], coins[i][1] + 1, coins[i][2]});
            if (coins[i + 1][0] != coins[i][1] + 1)
                new_coins.push_back({coins[i][1] + 1, coins[i + 1][0], 0});
        }
        new_coins.push_back({coins.back()[0], coins.back()[1] + 1, coins.back()[2]});

        n = new_coins.size();

        int p = new_coins[0][0], i = 0, j = 0;
        LL cur = 0;
        while (j < n && new_coins[j][1] < p + k) {
            cur += (LL)(new_coins[j][1] - new_coins[j][0]) * new_coins[j][2];
            ++j;
        }

        if (j < n)
            cur += (LL)(p + k - new_coins[j][0]) * new_coins[j][2];

        LL ans = cur;
        while (j < n) {
            if (new_coins[i][1] - p < new_coins[j][1] - (p + k)) {
                cur += (LL)(new_coins[i][1] - p) *
                    (new_coins[j][2] - new_coins[i][2]);
                p = new_coins[i][1];
                ++i;
            } else {
                cur += (LL)(new_coins[j][1] - (p + k)) *
                    (new_coins[j][2] - new_coins[i][2]);
                p = new_coins[j][1] - k;
                ++j;
            }

            ans = max(ans, cur);
        }

        return ans;
    }
};