题目描述

给你一个二维整数数组 intervals，其中 intervals[i] = [l_i, r_i, weight_i]。区间 i 的起点为 l_i，终点为 r_i，权重为 weight_i。你最多可以选择 4 个互不重叠 的区间。所选择区间的 得分 定义为这些区间权重的总和。

返回一个至多包含 4 个下标且 字典序最小 的数组，表示从 intervals 中选中的互不重叠且得分最大的区间。

如果两个区间没有任何重叠点，则称二者 互不重叠。特别地，如果两个区间共享左边界或右边界，也认为二者重叠。

样例

输入： intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]

输出： [2,3]

解释：

可以选择下标为 2 和 3 的区间，其权重分别为 5 和 3。

输入： intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]

输出： [1,3,5,6]

解释：

可以选择下标为 1、3、5 和 6 的区间，其权重分别为 7、6、3 和 5。

限制

• 1 <= intervals.length <= 5 * 10^4
• intervals[i].length == 3
• intervals[i] = [l_i, r_i, weight_i]
• 1 <= l_i <= r_i <= 10^9
• 1 <= weighti <= 10_9

算法

(动态规划) $O(n \log n)$

1. 如果结果不要求字典序最小，那可以直接用经典的动态规划求解。先将区间按照结束端点排序，然后设状态 $f(i, j)$ 表示遍历了前 $i$ 个区间，选了 $j$ 个区间的最大权重之和。
2. 如果要求字典序最小，在排序后的情况下，只能在动态规划的时候同时记录选中的下标列表，用来在更新的时候维护字典序。
3. 具体地，设状态 $f(i, j)$ 表示遍历了前 $i$ 个区间，选了 $j$ 个区间时，最大权重以及得到这个最大权重选择的下标列表。
4. 初始时，$f(0, j) = [INF] * 5$，$f(i, 0) = [0] + [INF] * 4$。
5. 转移时，对于第 $i$ 个区间，二分找到小于当前区间起点的最大区间位置 $l$，转移 $f(i, j) = \max(f(i - 1, j), f(l, j - 1) + w(i))$，其中 $w(i)$ 的计算就是取出 $f(l, j - 1)$ 的列表，然后更新权重之和和下标。
6. 最终答案为 $\max(f(n, j))$，然后手动处理下输出格式。

时间复杂度

• 假设选择的区间个数 $4$ 是常数，则状态数为 $O(n)$，转移时间为 $O(\log n)$，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态。

C++ 代码

#define LL long long

const int N = 50010;

class Solution {
private:
    int p[N];
    array<LL, 5> f[N][5];

public:
    vector<int> maximumWeight(vector<vector<int>>& intervals) {
        const int n = intervals.size();

        for (int i = 1; i <= n; i++)
            p[i] = i - 1;

        sort(p + 1, p + 1 + n, [&](int x, int y) {
            return intervals[x][1] < intervals[y][1];
        });

        for (int j = 1; j < 5; j++)
            f[0][j] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX};

        for (int i = 0; i <= n; i++)
            f[i][0] = {0, INT_MAX, INT_MAX, INT_MAX, INT_MAX};

        for (int i = 1; i <= n; i++) {
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (intervals[p[mid + 1]][1] < intervals[p[i]][0]) l = mid + 1;
                else r = mid;
            }

            for (int j = 1; j <= 4; j++) {
                array<LL, 5> t = f[l][j - 1];

                t[0] -= intervals[p[i]][2];
                t[j] = p[i];

                sort(t.begin() + 1, t.end());

                f[i][j] = min(f[i - 1][j], t);
            }
        }

        array<LL, 5> res = min(min(f[n][1], f[n][2]), min(f[n][3], f[n][4]));
        vector<int> ans;
        for (int j = 1; j <= 4 && res[j] < INT_MAX; j++)
            ans.push_back(res[j]);

        return ans;
    }
};