每日一题：最多可以参加的会议数目II

题意

给你一个 $a$ 数组，其中 $a[i] = [startDay_i, endDay_i, value_i]$ ，表示第 $i$ 个会议在 $startDay_i$ 天开始，第 $endDay_i$ 天结束，如果你参加这个会议，你能得到价值 $value_i$ 。同时给你一个整数 $k$ 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和。$(k \in [1, n], k * n \in [1, 1e6], startDay_i, endDay_i \in [1, 1e9], value_i \in[1, 1e6])$

Solution

考虑动态规划。$dp[i][j]$ 表示前 $i$ 个会议刚好选 $j$ 个时，能获得的最大价值。

那么对于每个 $dp[i][j]$ 有两种情况：

• 不参加第 $i$ 个会议，有 $dp[i][j] = dp[i - 1][j]$
• 参加第 $i$ 个会议，设第 $i$ 个会议开始时间为 $l$，那么我们应该是从 所有结束时间小于 $l$ 且刚好选 $j - 1$ 个会议 的那个状态转移过来。那么最好的方式就是一开始就将 $a$ 按结束时间排序，这样我们就能很快二分出来结束时间刚好（最后一个）小于 $l$ 的那个会议 $p$，有 $dp[i][j] = max(dp[i][j], dp[p][j - 1] + a[i].value)$。

时间复杂度 $O(nklog_n)$。

Code

class Solution {
public:
    struct Node {
        int l, r, w;
        bool operator< (const Node& a) const{
            return r < a.r;
        }
    };
    int maxValue(vector<vector<int>>& a, int k) {
        int n = a.size();
        vector<Node> q(n + 1);
        vector<vector<int>> dp(n + 1, vector<int> (k + 1));
        for (int i = 0; i < n; i++) q[i + 1] = {a[i][0], a[i][1], a[i][2]};
        sort(q + 1, q + n + 1);
        for (int i = 1; i <= n; i++) {
            int l = 0, r = i, mid;
            while (l + 1 < r) {
                mid = l + r >> 1;
                if (q[mid].r < q[i].l) l = mid;
                else r = mid;
            }
            for (int j = 1; j <= k; j++) 
                dp[i][j] = max(dp[i - 1][j], dp[l][j - 1] + q[i].w);
        }
        return dp[n][k];
    }
};