贪心算法

思想

• 贪心算法可以认为是动态规划算法的一个特例

• 每一步都做出一个局部最优的选择，最终的结果就是全局最优

框架

• 贪心算法没有固定解法套路

• 以【最多有多少无重叠区间】为例

  • 1. 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。

  • 2. 把所有与 x 区间相交的区间从区间集合 intvs 中删除。

  • 3. 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集

var eraseOverlapIntervals = function(intervals) {
    if(intervals.length<2) return intervals.length;

    // 递增排序
    intervals.sort((a,b)=>a[1]-b[1])

    let count = 1,
        _end = intervals[0][1];

    for(const inter of intervals){
        const _start = inter[0];
        // 无重合则count+1 重置右边界
        if(_start >= _end){
            _end = inter[1];
            count++
        }
    }
    return count
};