【完整题单10、贪心与思维(区间合并)】【✅✅✅✅】

目录知识框架No.0 筑基No.1 区间数组题目来源Acwing-803. 区间合并题目来源LeetCode-56. 合并区间No.2 数字数组题目来源LeetCode-495. 提莫攻击知识框架No.0 筑基请先学习下知识点道友题目知识点大部分来源于此题目例题大部分来源于此Y总的模板来自Acwing如下// 将所有存在交集的区间合并voidmerge(vectorPIIsegs){vectorPIIres;sort(segs.begin(),segs.end());intst-2e9,ed-2e9;for(autoseg:segs)if(edseg.first){if(st!-2e9)res.push_back({st,ed});stseg.first,edseg.second;}elseedmax(ed,seg.second);if(st!-2e9)res.push_back({st,ed});segsres;}No.1 区间数组题目来源Acwing-803. 区间合并题目描述题目思路题目代码#includeiostream#includealgorithm#includevectorusingnamespacestd;typedefpairint,intPII;intn,l,r;vectorPIIsegs;voidmerge(vectorPIIsegs){vectorPIIres;sort(segs.begin(),segs.end());//按区间左端点排序sort默认排序segs的第一项intst-2e9,ed-2e9;//此时st和ed只要比-1e9小就可以for(autoseg:segs){if(edseg.first){if(st!-2e9)res.push_back({st,ed});stseg.first;edseg.second;}elseedmax(ed,seg.second);}if(st!-2e9)res.push_back({st,ed});segsres;//不能忘}intmain(){cinn;for(inti0;in;i){cinlr;segs.push_back({l,r});}merge(segs);coutsegs.size()endl;return0;}//该代码引用AcWing网站的代码题目来源LeetCode-56. 合并区间题目描述题目思路贪心题目代码classSolution{public:vectorvectorintmerge(vectorvectorintintervals){intnintervals.size();if(n0)return{};//很明显的区间合并// 先根据。起始点start进行排序vectorpairint,intans;for(autointer:intervals){ans.push_back(pairint,int(inter[0],inter[1]));}sort(ans.begin(),ans.end());vectorvectorintres;res.push_back({ans[0].first,ans[0].second});for(inti1;in;i){autolast_resres.back();autolast_startlast_res[0];autolast_endlast_res[1];autonow_ansans[i];autonow_startnow_ans.first;autonow_endnow_ans.second;if(now_startlast_end){if(now_endlast_end){continue;}else{last_endnow_end;}}else{res.push_back({now_start,now_end});}}returnres;}};No.2 数字数组题目来源LeetCode-495. 提莫攻击题目描述题目思路感觉像是 区间合并但是 贪心也行吧题目代码classSolution{public:intfindPoisonedDuration(vectorinttimeSeries,intduration){intntimeSeries.size();if(n0)return0;// sort(timeSeries.begin(), timeSeries.end());// 非递减;intres0;intendtimeSeries[0]duration;resduration;for(inti1;in;i){autonow_endtimeSeries[i]duration;autonow_setimeSeries[i];if(now_seend){// 无间隙续上resres(now_end-end);}else{// 没有续上resresduration;}// 新的endendnow_end;}returnres;}};