# 贪心算法

# 1、贪心算法概念

贪⼼算法其实可以认为是dp问题的⼀个特例, 除了动态规划的各种特征外, 贪⼼算法还需要满⾜”贪⼼选择性质”, 当然效率也⽐动态规划要⾼。贪心选择性质：每一步都会做出一个局部最优的选择，最终的结果就是全局最优。

满足贪心选择性质：⽐如你前⾯堆满了⾦条, 你只能拿5根, 怎么保证拿到的价值最⼤？答案当然是：每次都拿剩下的⾦条中最重的那根, 那么最后你拿到的⼀定是最有价值的。
不满足贪心选择性质：⽐如⽃地主, 对⽅出了⼀个3, 你⼿上有345678还有⼀个2, 按照贪⼼选择, 这时候你应该出4了, 实际上咱们会尝试出2, 然后345678起⻜

# 2、区间调度算法

有许多[start, end]的闭区间，请设计⼀个算法，算出这些区间中最多有⼏个互不相交的区间。

应用场景：⽐如你今天有好⼏个活动可以参加,，每个活动区间⽤[start, end]表示开始和结束时间，请问你今天最多能参加⼏个活动？

// ⽐如intvs = [[1,3], [2,4], [3,6]]
// 这些区间最多有两个区间互不相交, 即 [1,3], [3,6], intervalSchedule函数此时应该返回2
function intervalSchedule(intvs: number[][]) {}

1
2
3

# 1、解题思路

每次选择可选区间中开始最早的那个？

不⾏，因为可能有的区间开始很早，结束很晚, ⽐如[0,10]，使我们错过了很多短区间⽐如[1,2]，[2,3]
每次选择可选区间中最短的那个？

不⾏，直接看上⾯这个例⼦[1,3]，[2,4]，[3,6], 这样的话会选择出 [1, 3]，[2, 4], 并不能保证他们不相交
正确思路：结合2和1
1. 从可选区间intvs⾥，选择⼀个end最⼩的区间x，即结束时间最小的区间
2. 把所有与x相交的区间从intvs中剔除，保证不相交
3. 重复1和2步骤，直到intvs为空，之前选出的各种区间x，就是我们要求的结果

# 2、代码实现

选出end最⼩的区间

对区间根据end升序排序，选择第⼀个区间即可
剔除与x相交的区间

升序区间中，只有begin大于第一个区间的end值才不相交
循环遍历区间，将最小区间更新即可

// 有许多[start, end]的闭区间, 请设计⼀个算法, 算出这些区间中, 最多有⼏个互不相交的区间
// intvs = [[1,3], [2,4], [3,6]]
// 最多有两个区间互不相交，即[1,3]，[3,6]，intervalSchedule函数返回2

function intervalSchedule(intvs){
    if(intvs.length === 0){
        return 0;
    }
    //1. 根据end时间升序排序
    const sortArray = intvs.sort((a, b) => a[1] - b[1]);
    let count = 1; //不相交的区间，至少有一个
    let xEnd = sortArray[0][1];

    for(let item of intvs){
        const start = item[0];
        if (start >= xEnd){
            count++;
            xEnd = item[1];
        }
    }
    
    return count;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 3、无重叠区间

给定⼀个区间的集合，找到需要移除区间的最⼩数量，使剩余区间互不重叠。

注意：可以认为区间的终点总是⼤于它的起点，区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

eg：输入： [ [1,2], [2,3], [3,4], [1,3] ]，输出：1，移除[1,3]后，剩余区间没有重叠。

解题思路：找到了最多有⼏个互不相交的区间数n，那么总数减去n就可以了。

function eraseOverlapIntervals(intervals){
		if (intervals.length === 0){
      return 0;
    }
    let sortArray = intervals.sort((a, b) => a[1] - b[1]);
    let count = 1;
    let xEnd = sortArray[0][1];
    for (let item of intervals){
      if (item[0] >= xEnd){
        count++;
        xEnd = item[1];
      }
    }
    return intervals.length - count;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 4、用最小的箭头射爆气球

在⼆维空间中有许多球形的⽓球。对于每个⽓球，提供的输⼊是⽔平⽅向上，⽓球直径的开始和结束坐标。由于它是⽔平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就⾜够了。开始坐标总是⼩于结束坐标。平⾯内最多存在104个⽓球。⼀⽀⼸箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出⼀⽀箭，若有⼀个⽓球的直径的开始和结束坐标为 xstart，xend，且满⾜ xstart ≤ x ≤ xend，则该⽓球会被引爆。可以射出的⼸箭的数量没有限制。⼸箭⼀旦被射出之后，可以⽆限地前进。我们想找到使得所有⽓球全部被引爆，所需的⼸箭的最⼩数量。

eg：输入[10,16], [2,8], [1,6], [7,12]，输出2，我们可以在x = 6（射爆[2,8]，[1,6]两个⽓球）和 x = 11（射爆另外两个⽓球）。

解题思路：如果最多有n个不重叠的空间, 那么就⾄少需要n个箭头穿透所有空间，所以我们要求的其实就是最多有⼏个不重叠的空间。注意：边界重叠后, 箭头是可以⼀起射爆的, 所以两个区间的边界重叠也算是区间重叠。