介绍

贪心算法，总是在对问题求解的时候作出局部当前最优的选择，须注意的是，当前的状态不会受到以后的状态/阶段选择的影响，只和当前的状态有关。求解贪心算法的基本思路如下：

  • 建立数学模型来描述问题。
  • 将求解的问题分解成为若干个小问题。
  • 每次对小问题求解，总是得到子问题的局部最优解。
  • 将每一次局部最优解合并，就是整体最优解。

但是贪心算法也有自己的缺陷：

  • 不能保证最后求得的是最佳解法。
  • 不能用来求解最大值或者最小值。

柠檬水找零

问题描述

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。

求解思路

主要的思路是不断地将金额和纸币面额按照从大到小对比，如果金额大于纸币面额，那么就计算该面额纸币的张数。然后剩下的用更小的面额对比即可。

/**
 * @param {number[]} bills
 * @return {boolean}
 */
 var lemonadeChange = function(bills) {
     const coins={
         5:0,
         10:0,
         20:0
     }
     function exchange(amount){
        while(amount>=20&&coins[20]>0){
            amount-=20
             coins[20]--
        }
        while(amount>=10&&coins[10]>0){
            amount-=10
            coins[10]--
        }
        while(amount>=5&&coins[5]>0){
            amount-=5
             coins[5]--
        }
        return amount===0
    }
     for(let bill of bills){
         coins[bill]++
         if(!exchange(bill-5)) return false
     }
     return true
};

合并区间

问题描述

上学那会，体育课没少被占用，课程总是安排得满满的。假设现在我们是教导主任，学校有个活动日，提供很多备选的活动，活动有开始时间、结束时间和活动名称。现在你需要实现一个算法，能够自主根据提供的活动开始/结束时间，安排一天的活动，要求安排的活动越多越好。

数据：

// 开始时间  结束时间
3 5
1 4
5 7
0 6
6 10
3 8
5 9
8 12
8 11
2 13
12 14

求解思路

用贪心算法解决。

区间集合，要将重叠区间合并，需要排序，以便找到重叠区间。

对于区间集合进行排序有两个选择，对于左边界或者右边界进行排序。

排序后，找重叠部分，对于左边界进行排序，如果一个区间的右边界大于等于下一个区间的左边界，表明这两个区间有重叠部分，要将前一个区间的右边界拓宽，选择这两个区间中较大的右边界。

如果一个区间的右边界小于下一个区间的左边界，这两个区间没有重叠，将前一个区间加入结果集合中。

遍历结束后还要将最后一个区间加入结果集合中。

代码实现

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  let res = [];
  intervals.sort((a, b) => a[0] - b[0]);

  let prev = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    let cur = intervals[i];
    if (prev[1] >= cur[0]) { // 有重合
      prev[1] = Math.max(cur[1], prev[1]); 
    } else {       // 不重合，prev推入res数组 
      res.push(prev);
      prev = cur;  // 更新 prev
    }
  }

  res.push(prev);
  return res;
};