leetcode 1235. 規劃兼職工作(就是活動安排，每個活動有個報酬，問你得到最大報酬，dp)

題目

把活動按結束時間從小到大排序，對于每個活動求出前面最後一個結束時間<=該活動開始時間的活動，

把活動的結束時間插入到線段樹，求前面最後一個<=，就是求前面第一個> 然後-1.

dp[i]=max(dp[i-1],profit[i]+dp[pre[i]]); dp[i]:代表前i個活動安排獲得的最大報酬。

class Solution {
public:
    struct Segment{
        int mx[50000<<2]={0};
        void insert(int dex,int val,int l,int r,int pos){
            if(l==r) {mx[pos]=val;return;}
            int mid=(l+r)>>1;
            if(dex<=mid) insert(dex,val,l,mid,pos<<1);
            else insert(dex,val,mid+1,r,pos<<1|1);
            mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);
        }
        int query(int val,int l,int r,int pos){
            if(l==r) return l;
            int mid=(l+r)>>1;
            if(mx[pos<<1]>val) return query(val,l,mid,pos<<1);
            return query(val,mid+1,r,pos<<1|1);
        }
    }A;
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n=startTime.size(),*a=new int[n],*pre=new int[n],*dp=new int[n];
        for(int i=0;i<n;++i) a[i]=i;
        sort(a,a+n,[&](int& x,int &y)->bool{return endTime[x]<endTime[y];});
        A.insert(1,endTime[a[0]],1,n,1);
        for(int i=1;i<n;++i){
            //找到最右邊小于等于startTime[a[i]]的
            if(A.mx[1]<=startTime[a[i]]) pre[i]=i-1;
            else pre[i]=A.query(startTime[a[i]],1,n,1)-2;
            A.insert(i+1,endTime[a[i]],1,n,1);//将endTime[a[i]]插入到線段樹中
        }
        dp[0]=profit[a[0]];
        for(int i=1;i<n;++i) dp[i]=profit[a[i]]+((pre[i]==-1)?0:dp[pre[i]]),dp[i]=max(dp[i],dp[i-1]);
        return dp[n-1];
    }
};