代码随想录算法训练营第三十九天（贪心算法篇）| 406. 根据身高重建队列， 452. 用最少数量的箭引爆气球

406.根据身高重建队列

资料：代码随想录 (programmercarl.com)

题目大意：数组people表示队列中一些人的属性（不一定按顺序）。每个?people[i] = [hi, ki]?表示第?i?个人的身高为?hi?，前面?正好?有?ki?个身高大于或等于?hi?的人。返回数组queue，是?queue[j] = [hj, kj]?可以正确表示队列中第?j?个人的属性（queue[0]?是排在队列最前面的人）。

思路

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]，以[4,4]为例，它在queue中，前面有四个比它大或等于它的数组，但people中全部数组都满足这一点，所以不管其它数组的顺序如何，它一定在第四个。如果可以理解这个想法，其实稍加扩展就能得到完整的思路：找到比当前数组大的元素，根据它的k值插入它们当中。

题目涉及到两个维度，h和k，要先确定一个维度后，再根据第二个维度调整。先按k排列的无意义，因此先按照身高从大到小排列（如果身高相同，按照k从小到大），这样保证每一组前面的身高比它高。再根据每组的k，插入到queue中。从身高最高的开始插入，这样后序插入节点也不会影响前面已经插入的节点（因为前面已经插入的节点一定都比它高）。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

Python基础语句

sort

对于一个嵌套数组，直接使用sort函数，会现根据数组元素第一个大小按顺序排，如果相同，在依次比较后一个。而对于这道题目，需要按第一个元素从大到小，相同情况下按第二个从小到大，可以借助lambda函数:

people.sort(key = lambda x:(-x[0], x[1]))

insert函数

queue.insert(order, item)
# order: 插在第几位  item：要插入的元素

代码实现

class Solution(object):
    def reconstructQueue(self, people):
        people.sort(key = lambda x:(-x[0], x[1]))
        queue = []
        for item in people:
            queue.insert(item[1], item)
        return queue

452. 用最少数量的箭引爆气球

题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

题目大意

一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组?points?，其中points[i] = [xstart, xend]?表示水平直径在?xstart?和?xend之间的气球。不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点?完全垂直?地射出。在坐标?x?处射出一支箭，若有一个气球的直径的开始和结束坐标为?xstart，xend，?且满足 ?xstart?≤ x ≤ xend，则该气球会被?引爆?。可以射出的弓箭的数量?没有限制?。 弓箭一旦被射出之后，可以无限地前进。

思路

如果两个区间有交集，可用一只箭引爆，多个气球最少需要的箭为总气球的数量减去交集的次数。先将数组从小到达排序，如果后一个的xstart在前一个的区间之间，则重叠，更新区间（取两个区间的交集），如果不重叠，新的区间为当前的points。也可以直接统计需要箭的数量，即如果后一个的xstart在上一个xend的右边，就加一支。

代码实现

class Solution(object):
    def findMinArrowShots(self, points):
        points.sort()
        interval = points[0]
        overclap = 0
        for i in range(1, len(points)):
            if points[i][0] <= interval[1] and points[i][0] >= interval[0]:
                overclap += 1
                interval[0] = points[i][0]
                interval[1] = min(points[i][1], interval[1])
            else:
                interval = points[i]
        return len(points) - overclap 

class Solution(object):
    def findMinArrowShots(self, points):
        points.sort()
        interval = points[0]
        bow = 1
        for i in range(1, len(points)):
            if points[i][0] > interval[1] :
                bow += 1
                interval[0], interval[1] = points[i][0], points[i][1]
            else:
                interval[0] =points[i][0]
                interval[1] = min(points[i][1], interval[1])
           
        return bow

35. 无重叠区间

题目链接：435. 无重叠区间 - 力扣（LeetCode）

思路

和上面“引爆气球”的思路很像，将intervals排序后，统计重叠次数，若重叠，取区间的交集（相当于留下范围小的区间，删掉范围大的，这样才能保证得到最小移除区间。），继续比较。

代码实现

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        space = intervals[0]
        num = 0
        for i in range(1, len(intervals)):
            if intervals[i][0] >= space[1]:
                space = intervals[i]
            else:
                num += 1
                space[1] = min(space[1], intervals[i][1])
        return num

也可以不用单独变量space，直接比较当前和前一个interval，看是否重叠。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort()  
        num = 0  
        
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:  # 存在重叠区间
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  
                num += 1
        
        return num