问题描述 链接到标题

1751.最多可以参加的会议数目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(这里是否等于取决于具体实现>=或者>)

代码 链接到标题 

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];
    }
};