贪心-摆动序列、不重叠字串数量

Ref

1. 贪心B站
2. 搜索-折半搜索

分发饼干

classSolution{public:intfindContentChildren(vector<int>&g,vector<int>&s){sort(g.begin(),g.end());sort(s.begin(),s.end());intcnt=0;for(inti=0,j=0;i<g.size()&&j<s.size();){if(s[j]>=g[i]){i++;j++;cnt++;}else{j++;}}returncnt;}};

最常规的贪心题目

公平分发饼干

值域大，有负数

非负-01背包

摆动序列

不重叠区间数量

classSolution{public:interaseOverlapIntervals(vector<vector<int>>&intervals){sort(intervals.begin(),intervals.end(),[](constvector<int>a,constvector<int>b){returna[1]<b[1];});intcnt=1;intsize=intervals.size();intend=intervals[0][1];for(inti=1;i<size;i++){if(intervals[i][0]>=end){cnt++;end=intervals[i][1];}}return(size-cnt);}};