【LeetCode - 1235. hard】规划兼职工作

题干：

先来看简单版本：

n个区间，求最大的不相交区间数

​​【51NOD—贪心算法专题】 D 做任务一 区间贪心+最大不相交子区间数_荷叶田田_的博客-CSDN博客​​

如果限定这道题的报酬都是1，那么就转化成【最大不相交区间数】了。 

那道题直接贪心即可（其中又分两种思路，右端点贪心，能选则选。左端点贪心，能选择试图选，有更优则取更优）

class Solution {
public:
    struct Node{
        int st,ed,p, i;
        Node(){}
        Node(int st, int ed, int p,int i):st(st), ed(ed), p(p),i(i){}
    };
    static bool cmp(Node a, Node b) {
        return a.ed < b.ed;
    }
    Node nn[500005];
    int dp[500005];
    vector<int >vv[500005];
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        set<int> ss;
        for(int i = 0; i<n; i++) {
            ss.insert(startTime[i]);
            ss.insert(endTime[i]);
        }
        map<int, int> mp;
        int cnt = 0; // [1, cnt]
        for(auto x : ss) {
            mp[x] = ++cnt;
        }
        for(int i = 0; i<n; i++) {
            nn[i] = Node{mp[startTime[i]], mp[endTime[i]], profit[i], i};
        }
        sort(nn, nn+n, cmp);
        for(int i = 0; i<n; i++) {
            vv[nn[i].ed].push_back(i);
        }
        //枚举时间点
        for(int i = 1; i<=cnt; i++) {
            dp[i] = dp[i-1];
            for(auto idx : vv[i]) {
                dp[i] = max(dp[i], dp[nn[idx].st]+nn[idx].p);
            }
        }
        return dp[cnt];
    }
};