# 1751.最多可以参加的会议数目II

## 问题描述
[1751.最多可以参加的会议数目II](https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended-ii/)

## 解题思路
动态规划+二分法
令`dp[i][j]`表示在前`i`个会议，最多参加`j`个会议，收获的最大价值:
- 考虑选择不参加`events[i - 1]`，`dp[i][j] = dp[i - 1][j]`;
- 选择参加`events[i - 1]`，`dp[i][j] = dp[idx][j - 1] + events[i - 1][2]`;
    - 其中`idx`表示结束日期小于`events[i - 1][0]`且最接近`events[i - 1][0]`的会议的索引号，因此这里需要**按照结束日期从小到大对`events`排序**;
    - 寻找`idx`可以使用二分查找;

二分查找要注意其中的不变量，即`l`左侧的值都小于`target`，`r`右侧的值都大于或等于`target`(这里是否等于取决于具体实现>=或者>)

## 代码
```cpp
class Solution {
  public:
    int maxValue(vector<vector<int>> &events, int k) {
        vector<vector<int>> dp(events.size() + 1, vector<int>(k + 1, 0));
        // 按照会议结束顺序排序
        std::sort(events.begin(), events.end(), [](auto &a, auto &b) { return a[1] < b[1]; });
        // for (int i = 1; i <= events.size(); i++) {
        //     dp[i][1] = events[i - 1][2];
        // }
        for (int i = 1; i <= events.size(); i++) {
            for (int j = 1; j <= k; j++) {
                int tmp1 = dp[i - 1][j]; // 不包含event[i - 1]的情况
                int find_idx = 0;
                int l = 0;
                int r = i - 2;
                for (; l <= r && r >= 0;) {
                    int mid = l + (r - l) / 2;
                    if (events[mid][1] >= events[i - 1][0]) {
                        r = mid - 1;
                        // mid = l + (r - l) / 2;
                    } else {
                        l = mid + 1;
                        // mid = l + (r - l) / 2;
                    }
                }
                // if (l == 0)
                //     dp[i][j] = std::max(tmp1, events[i - 1][2]);
                // else
                dp[i][j] = std::max(tmp1, dp[l][j - 1] + events[i - 1][2]);
            }
        }
        return dp[events.size()][k];
    }
};
```