(nice!!!)(LeetCode 每日一题) 1751. 最多可以参加的会议数目 II (动态规划+二分查找)

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

思路：动态规划+二分查找。时间复杂度0(n * (logn+k))。

先将活动数组events按结束时间升序排序，然后采用动态规划+二分查找求解，细节看注释。

C++版本：

class Solution {
public:
    typedef struct Node{
        int st,ed,val;
        bool friend operator<(struct Node a,struct Node b){
            return a.ed<b.ed;
        }
    }node;
    int maxValue(vector<vector<int>>& events, int k) {
    	//先将数组events按结束时间升序排序
        vector<node> v;
        // 加入一个哨兵活动，避免二分时越界
        v.push_back({0,0,0});
        for(auto x:events){
            v.push_back({x[0],x[1],x[2]});
        }
        sort(v.begin(),v.end());
        // 此时的n是已经加入哨兵后的n
        int n=v.size();
        // 状态f[i][j]:表示在0~i个活动时，最多选j个活动参与的“价值最大之和”
        vector<vector<int>> f(n+1,vector<int>(k+1));
        // 动态规划dp
        for(int i=1;i<n;i++){
        	//二分查找，找到最后一个活动结束时间比p小的活动
            int p=v[i].st;
            int l=0,r=i-1;
            while(l<r){
                int mid=(l+r+1)/2;
                if(v[mid].ed<p) l=mid;
                else r=mid-1;
            }
            //维护在0~i个活动下，最多选j个活动的最优解
            for(int j=1;j<=k;j++){
                f[i][j]=max(f[i-1][j],f[r][j-1]+v[i].val);
            }
        }
        return f[n-1][k];

    }
};

JAVA版本：

class Solution {
    class node {
        int st,ed,val;
        node(int st,int ed,int val){
            this.st=st;
            this.ed=ed;
            this.val=val;
        }
    }
    public int maxValue(int[][] events, int k) {
        List<node> v=new ArrayList<>();
        v.add(new node(0,0,0));
        for(var x:events){
            v.add(new node(x[0],x[1],x[2]));
        }
        Collections.sort(v,(a,b)-> a.ed-b.ed);
        int n=v.size();
        int[][] f=new int[n][k+1];
        
        for(int i=1;i<n;i++){
            int p=v.get(i).st;
            int l=0,r=i-1;
            while(l<r){
                int mid=(l+r+1)/2;
                if(v.get(mid).ed<p) l=mid;
                else r=mid-1;
            }
            for(int j=1;j<=k;j++){
                f[i][j]=Math.max(f[i-1][j],f[r][j-1]+v.get(i).val);
            }
        }
        return f[n-1][k];
    }
}

GO版本：

type node struct{
    st,ed,val int
}
func maxValue(events [][]int, k int) int {
    n:=len(events)
    v:=make([]node,n+1)
    v[0]=node{0,0,0}
    for i,x:=range events{
        v[i+1]=node{x[0],x[1],x[2]}
    }
    sort.Slice(v,func(a,b int) bool {
        return v[a].ed<=v[b].ed
    })
    f :=make([][]int ,n+1)
    f[0]=make([]int,k+1)
    for i:=1;i<=n;i++ {
        p:=v[i].st
        l,r:=0,i-1
        for l<r {
            mid:=(l+r+1)/2
            if v[mid].ed<p{
                 l=mid
            }else{
                r=mid-1
            }
        }

        f[i]=make([]int,k+1)
        for j:=1;j<=k;j++{
            f[i][j]=max(f[i-1][j],f[r][j-1]+v[i].val)
        }
    }
    return f[n][k]
}