Leetcode 1751. 最多可以参加的会议数目 II （DAY 71) ---- 动态规划学习期（下个星期要开始上高数了 每周三节捏马）

原题题目

代码实现（首刷超时 n^3时间复杂度）

bool cmp(const vector<int>& a,const vector<int>& b)
{
    if(a[1] < b[1] || a[1] == b[1] && a[2] < b[2]) return true;else   return false;
}class Solution {
    
public:int maxValue(vector<vector<int>>& events, int k) {
    sort(events.begin(),events.end(),cmp);int esize = events.size(),ret = -1;int endsize = (events.back())[1];vector<vector<int>> dp(k+1,vector<int>(endsize+1,0));for(int i=1;i<=k;i++){
    for(int j=0;j<esize;j++){
    for(int k=0;k<=events[j][0]-1;k++)dp[i][events[j][1]] = max(dp[i-1][k] + events[j][2],dp[i][events[j][1]]);ret = max(ret,dp[i][events[j][1]]);}}return ret;}
};

代码实现（优化版 n^3仍然超时 n^2*logn才不会超时）

bool cmp(const vector<int>& a,const vector<int>& b)
{
    if(a[1] < b[1] || a[1] == b[1] && a[2] < b[2]) return true;else   return false;
}class Solution {
    
public:int maxValue(vector<vector<int>>& events, int k) {
    sort(events.begin(),events.end(),cmp);int esize = events.size(),ret = -1;vector<vector<int>> dp(k+1,vector<int>(esize+1,0));for(int i=1;i<=k;i++){
    for(int j=0;j<esize;j++){
    dp[i][j] = fmax(events[j][2],dp[i][j]);for(int k=0;k<j;k++){
    if(events[k][1] <= events[j][0]-1)dp[i][j] = fmax(dp[i][j],dp[i-1][k] + events[j][2]);else break; }ret = max(ret,dp[i][j]);}}return ret;}
};

代码实现（别人的n^2*logn题解 二分加速）

class Solution {
    
public:static bool cmp(const vector<int>& x, const vector<int>& y) {
    return x[1] < y[1];}int maxValue(vector<vector<int>>& events, int k) {
    int n = events.size();sort(events.begin(), events.end(), cmp);vector<vector<int>> dp(n, vector<int>(k + 1, INT_MIN));dp[0][0] = 0;dp[0][1] = events[0][2];for (int i = 1; i < n; i++) {
    // 参加会议 i，此时需要二分查找int l = 0, r = i;while (r - l > 1) {
    int mid = (l + r) / 2;if (events[mid][1] >= events[i][0]) {
    r = mid;} else {
    l = mid;}}if (events[l][1] < events[i][0]) {
    for (int j = 1; j <= k; j++) {
    dp[i][j] = max(dp[i][j], dp[l][j-1] + events[i][2]);}} else {
    dp[i][1] = max(dp[i][1], events[i][2]);}// 不参加会议 ifor (int j = 0; j <= k; j++) {
    dp[i][j] = max(dp[i][j], dp[i-1][j]);}}int ret = 0;for (int i = 0; i <= k; i++) {
    ret = max(ret, dp[n-1][i]);}return ret;}
};