代码随想录算法训练营第33天 | 贪心4：452. 用最少数量的箭引爆气球、435. 无重叠区间 、763.划分字母区间

452.用最少数量的箭引爆气球
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
代码随想录
https://programmercarl.com/0452.用最少数量的箭引爆气球.html#算法公开课
435.无重叠区间
https://leetcode.cn/problems/non-overlapping-intervals/
代码随想录
https://programmercarl.com/0435.无重叠区间.html#其他语言版本

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

题解思路

• 统计最小右区间是否和新区间的左边重合
• 统计数据

题解代码

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key = lambda x:x[0])
        print(points)
        sl,sr = points[0][0],points[0][1]
        res = 1
        for i in points:
            if i[0]>sr:
                res +=1
                sr = i[1]
                ## 如果前后不重叠 则需要射出一箭 右边界更新
            else:
                sr = min(i[1],sr)
        return res

435. 无重叠区间

题解思路：

• 计算不重叠区间的个数 总体-不重叠区间
• 以右区间排序 （左右都可以）

题解代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x:x[1])
        sr = intervals[0][1]
        res = 1
        for i in intervals:
            if i[0]>=sr:
                res+=1
                sr = i[1]
                ##计算不重叠的区间
            else:
                sr = min(i[1],sr)
        return len(intervals)-res

763.划分字母区间

题解思路

• 记录每个字母最后的位置
• 划分字母的最后位置

题解代码

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        start_dic = {}
        for i in range(len(s)):
            start_dic[s[i]] = i
        print(start_dic)
        end = 0
        start = 0
        res = []
        for j in range(len(s)):
            end = max(end,start_dic[s[j]])
            if j==end:
                res.append(end-start+1)
                start = j+1
        return res