公司微信网站建设方案模板,常见的电子商务网站有,wordpress的注册文件在哪个文件夹,如何做网站电话题干#xff1a; 先来看简单版本#xff1a;
n个区间#xff0c;求最大的不相交区间数
【51NOD—贪心算法专题】 D 做任务一 区间贪心最大不相交子区间数_荷叶田田_的博客-CSDN博客
如果限定这道题的报酬都是1#xff0c;那么就转化成【最大不相交区间数】了。
那道题…题干 先来看简单版本
n个区间求最大的不相交区间数
【51NOD—贪心算法专题】 D 做任务一 区间贪心最大不相交子区间数_荷叶田田_的博客-CSDN博客
如果限定这道题的报酬都是1那么就转化成【最大不相交区间数】了。
那道题直接贪心即可其中又分两种思路右端点贪心能选则选。左端点贪心能选择试图选有更优则取更优
这道题带权值了所以加个dp
官方题解是dp二分我这种写法是离散化枚举dp我的代码复杂度更高一些可以直接看官网做法。
AC代码
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];vectorint vv[500005];int jobScheduling(vectorint startTime, vectorint endTime, vectorint profit) {int n startTime.size();setint ss;for(int i 0; in; i) {ss.insert(startTime[i]);ss.insert(endTime[i]);}mapint, int mp;int cnt 0; // [1, cnt]for(auto x : ss) {mp[x] cnt;}for(int i 0; in; i) {nn[i] Node{mp[startTime[i]], mp[endTime[i]], profit[i], i};}sort(nn, nnn, cmp);for(int i 0; in; i) {vv[nn[i].ed].push_back(i);}//枚举时间点for(int i 1; icnt; 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];}
};
