什么是贪心算法？

含义和其名字一样，贪心：要最大的、最小的、最多的、最少的.....

如：将s个糖果分给g个孩子，每个糖果大小为si，每个孩子至少分到gi大小的糖果才开心，那么求问：怎么分能让更多的孩子开心。

这里可以考虑将si和gi按大小排序后，最先将最大的糖果分给gi最大的孩子，如果满足不了，则分给gi第二大的孩子，依次这样分下去。这种分法就是贪心算法核心所在。

贪心算法难度：

算法不难，算法代码也不难，难就难在如何判断该问题是否可用贪心算法解题。

贪心算法证明方法：

通常用反正法，如举出反例。

但是有些情况，很难举出返例，则可用反证法证明。如重叠区间问题中，end[i]>end[j]，假设end[i]满足最优解，但是此时end[j]比end[i]更小，说明end[j]才是满足最优解的区间，这和假设矛盾，所以可证明end越早结束，则给后面越多空间存在更多的非重叠区间。

最佳实践：

/** * 题目：有多个区间，请问至少删除多少个区间后没有重叠区间。 * 思路：题目可转换为求：至多有多少个不重叠区间。       方法一：动态规划，类似求最长子序列.       方法二：贪心算法，后一个区间的start大于等于前一个区间的end时算一个不重叠区间.*/struct Interval {  Interval() : start(0), end(0) {};  Interval(int start, int end) : start(start), end(end) {};  int start;  int end;};bool compare(Interval& lh, Interval& rh) {  if (lh.start != rh.start)    return lh.start < rh.start;  return lh.end < rh.end;}bool compare_end(Interval& lh, Interval& rh) {  if (lh.end != rh.end)    return lh.end < rh.end;  return lh.start < rh.start;}// 方法一：动态规划.int eraseOverlapIntervals(vector<Interval>& intervals) {  //1. 代码鲁棒性  if (intervals.size() == 0) return 0;  //2. 对每个区间排序.  sort(intervals.begin(), intervals.end(), compare);  //3. memo[i]表示使用Interval[0...i]的区间能构成的最长不重叠区间序列数.  vector<int> memo = vector<int>(intervals.size(), 1); // 因为每一个区间都可成为一个不重叠区间.    //4. 考虑interval[0...i]的区间能构成的最长不重叠区间序列数.  for (int i = 1; i < intervals.size(); i++) {    for (int j = 0; j <= i; j++) {      if (intervals[i].start >= intervals[j].end) {        memo[i] = max(memo[i], 1+memo[j]);      }    }  }  //5. 找出最大区间数.  int res = 0;  for (int i = 0; i < memo.size(); i++) {    res = max(res, memo[i]);  }  //6. 求出最少删除多少个区间后无重叠区间.  return intervals.size() - res;}// 方法二：贪心算法int eraseOverlapIntervalsGreedy(vector<Interval>& intervals) {  if (intervals.size() == 0) return 0;  sort(intervals.begin(), intervals.end(), compare_end);  int res = 1;  int pre = 0;  for (int i = 1; i < intervals.size(); i++) {    if (intervals[i].start >= intervals[pre].end) {      res++;      //pre++;  //Error.      pre = i;    }  }  return intervals.size() - res;}