代码随想录学习Day 31

435.无重叠区间

题目链接

讲解链接

本题思路与前一道类似，代码只需稍作修改。当后一个区间左边界小于前一个区间右边界时说明这两个区间存在重叠部分，此时将count + 1，并更新右边界为二者中较小的值即可。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])  # 按照区间左边界排序
        count = 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])  # 更新右边界，取两个区间右边界的最小值
                count += 1  # 重叠数+1
        return count

763.划分字母区间

题目链接

讲解链接

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {}
        for i, ch in enumerate(s):
            last_occurrence[ch] = i
        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_occurrence[ch])
            if i == end:
                result.append(end - start + 1)
                start = i + 1
        return result

56.合并区间

题目链接

讲解链接

本题与之前的无重叠区间和射气球类似，其实就是合并区间后将得到的左边界和右边界作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:  # 若数组长度为1则直接返回
            return intervals
        intervals.sort(key=lambda x:x[0])  # 按照左边界进行排序
        result = []  # 保存结果
        left, right = intervals[0][0], intervals[0][1]  # 初始化左右边界
        for i in range(len(intervals)):
            if intervals[i][0] <= right and intervals[i][1] >= right:  # 如果当前区间与左右边界有重叠部分
                right = intervals[i][1]  # 更新右边界
            elif intervals[i][0] > right:  # 如果当前区间与左右边界无重叠部分
                result.append([left, right])  # 将之前的边界加入结果集
                left = intervals[i][0]  # 更新左边界
                right = intervals[i][1]  # 更新右边界
        result.append([left, right])  # 将最后一个结果添加到结果中
        return result