LeetCode 1751. 最多可以参加的会议数目 II（DP + 二分查找）

输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。

输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。
 
提示：
1 <= k <= events.length
1 <= k * events.length <= 10^6
1 <= startDayi <= endDayi <= 10^9
1 <= valuei <= 10^6

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        sort(events.begin(), events.end(),[&](auto a, auto b){
            return a[1] < b[1];//结束时间排序
        });
        int n = events.size();
        vector<vector<int>> dp(n, vector<int>(k+1, -1));
        // dp[i][k] 表示 遍历完 第 i 个会议，开了k次会，的最大收益
        dp[0][0] = 0;
        dp[0][1] = events[0][2];
        for(int i = 1; i < n; i++)//转移到i会议，查找之前可以转移过来的j
        {   
            // 二分查找时间不冲突的，最晚的结束的会议 j
            int l = 0, r = i-1, mid, j = n;
            while(l <= r)
            {
                mid = l+((r-l)>>1);
                if(events[mid][1] >= events[i][0])//时间冲突
                    r = mid-1;
                else
                {
                    if(mid==n-1 || events[mid+1][1] >= events[i][0])
                    {
                        j = mid;
                        break;
                    }
                    else
                        l = mid+1;
                }
            }
            // i 会议不开
            for(int t = 0; t <= k; ++t)
                dp[i][t] = max(dp[i][t], dp[i-1][t]);
            // 没有可以转移到 i 的会议
            if(j == n) //只能开一个会议，i
                dp[i][1] = max(dp[i][1], events[i][2]);
            else // j 可以转移到 i 会议
                for(int t = 0; t < k; ++t)//原来开了多少次会
                {
                    dp[i][t+1] = max(dp[i][t+1], dp[j][t]+events[i][2]);
                }
        }
        int ans = 0;
        for(int t = 0; t <= k; ++t)
            ans = max(ans, dp[n-1][t]);
        return ans;
    }
};