代码随想录算法训练营第三十六天| LeetCode435. 无重叠区间、LeetCode763. 划分字母区间、LeetCode56. 合并区间

一、LeetCode435. 无重叠区间

        1：题目描述（435. 无重叠区间）

        给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

        2：解题思路

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals: return 0
        # 对intervals进行排序，按右边界进行排序
        intervals.sort(key=lambda x: x[1])      
        count = 1      # 记录非交叉区间的个数，初始为1
        end = intervals[0][1]    # 记录区间的分割点
        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                # 若当前元素的左边界值 大于等于 区间分割点，说明区间不相交
                count += 1       # 非交叉区间的个数+1
                # 更新区间的分割点，为当前元素的右边界值
                end = intervals[i][1]
        # 数组长度减去非交叉区间的个数，就是交叉区间的个数，及需要移除的最小区间
        return len(intervals)-count

二、LeetCode763. 划分字母区间

        1：题目描述（763. 划分字母区间）

        字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

        2：解题思路

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 先统计出每个字母在字符串中出现的最远位置
        hash_list = [0] * 26        # 初始化
        for i in range(len(s)):
            # 遍历字符串，记录元素出现的最远位置的下标
            hash_list[ord(s[i]) - ord("a")] = i
        result = []
        right = 0      # 切割字符串的右边界
        left = 0       # 切割字符串的左边界
        for i in range(len(s)):
            # 在right和当前元素的最远距离中取最大值
            right = max(right, hash_list[ord(s[i])-ord("a")])
            if i == right:
                # 当下标等于right，就可以切割字符串了
                # result.append(len(s[left:right+1]))
                result.append(right-left+1)
                # 下一个切割的左边界为i+1
                left = i + 1
        return result

三、LeetCode56. 合并区间

        1：题目描述（56. 合并区间）

        以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

        2：解题思路

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        if not intervals: return res
        intervals.sort(key=lambda x: x[0])
        res.append(intervals[0])
        for i in range(1, len(intervals)):
            last = res[-1]
            if intervals[i][0] <= last[1]:
                res[-1] = [last[0], max(last[1], intervals[i][1])] 
            else:
                res.append(intervals[i])
        return res