题目1：饼干分配

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

• 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；

• 并且每块饼干 j，都有一个尺寸 s[j] 。

如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

题目分析

就是每次取当前饼干最大值去满足当前胃口值最大的孩子。

既然涉及到了最大值，那么一定会用到排序

class Solution {
public:int findContentChildren(vector& g, vector& s) {//s:饼干，g:胃口/*排序*///从大到小sort(g.begin(),g.end(),greater());sort(s.begin(),s.end(),greater());/*两个索引+记录*/int g_index=0;int s_index=0;int res=0;/*算法：大饼干优先满足大胃口*/while(g_index=g[g_index]){//可分配res++;s_index++;g_index++;}else{//放弃大胃口孩子g_index++;}}return res;}
};

贪心算法与动态规划

题目2：没有重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠

在一个点上的重叠不叫区间重叠：【1，2】，【2，3】不重叠

示例

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠

把问题改成：最多保留多少区间，使得区间没有重叠

方法一：动态规划

bool compare(const vector& a,const vector& b){if(a[1]!=b[1]) return a[1]
public:int eraseOverlapIntervals(vector>& intervals) {if(intervals.size()==0) return 0;sort(intervals.begin(),intervals.end(),compare);/*动态规划*///最少也会选择一个区间，初始化为1//memo[i]:前i个区间可选择的不重叠的最大区间个数vector memo(intervals.size(),1);//两重遍历for(int i=1;ifor(int j=0;jif(intervals[i][0]>=intervals[j][1]){memo[i]=max(memo[i],memo[j]+1);}}}//选择最大的memo值int res=1;for(int i=0;i

bool compare(const vector& a,const vector& b){if(a[1]!=b[1]){return a[1]
public:int eraseOverlapIntervals(vector>& intervals) {/*边界处理*/if(intervals.size()==0) return 0;/*依据区间结束的大小进行排序*/sort(intervals.begin(),intervals.end(),compare);/*贪心过程*/int res=1;//sort的第一个区间必选int pre=0;for(int i=1;i//当前区间i的头>=前一个区间pre的尾if(intervals[i][0]>=intervals[pre][1]){res++;pre=i;}}return intervals.size()-res;}
};