今日任务：

1. LeetCode435 无重叠区间
2. LeetCode763 划分字母区间
3. LeetCode56 合并区间

资料来源：

1. 代码随想录 | LeetCode435 无重叠区间
2. 代码随想录 | LeetCode763 划分字母区间
3. 代码随想录 | LeetCode56 合并区间

1 LeetCode435 无重叠区间

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

要找的是需要被移除的重叠区间的最小数量，那我反向去找没有重叠区间的最大数量，再用所有区间的数量减去求出的没有重叠区间的最大数量，就能得到答案。

求没有重叠区间的数量，首先需要对给定的输入区间进行排序。排序标准可以是区间开始位置，也可以是区间结束位置，两种思路大体相同，下面的代码的排序依据是区间结束位置，排序后从第一个区间开始找起，记录区间结束位置，然后对之后的区间的开始位置进行挨个比较：如果之后的区间的开始位置小于记录的结束位置，说明这个区间和记录的结束位置对应的区间重叠，继续看下一个区间；如果之后的区间的开始位置大于记录的结束位置，说明这个区间和结束位置对应的区间不重叠，没有重叠区间的数量+1，将记录的结束位置更新为这个区间的结束位置，继续找和这个区间不重叠的下一个区间，直到循环结束。如果按照区间开始位置进行排序，比较思路也不变。

另外，这道题可以用上一道射气球题的思路来做，那道题在实际上找的是最少的不重叠区间。

python
from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        non_overlap_num = 0
        pointer = intervals[0][1]
        length = 0
        for i in intervals:
            length += 1
            if i[0] < pointer:  # 记录的区间结束位置和每个区间的开始位置比较
                continue
            else:
                non_overlap_num += 1
                pointer = i[1]
        return length - (non_overlap_num + 1)  # 因为循环结束后最后一个区间没加上 这里再加上

2 LeetCode763 划分字母区间

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

输入：s = "eccbbbbdec"
输出：[10]

首先先统计每个字母对应的区间起始和结束位置（这个统计过程其实也就自动排序了），然后还是记录区间的结束位置，挨个和之后区间的结束位置对比，如果区间的结束位置小于记录位置，就说明记录位置对应的区间能够完全将当前区间包括住；如果区间的结束位置大于记录位置，看区间的起始位置是否大于记录位置：如果是，则说明当前区间和记录位置对应的区间是不重叠的，在这里划分；如果不是，则说明重叠，修改记录的结束位置到当前区间的结束位置，继续循环对比。

python
from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        map = dict()
        for i in range(len(s)):  # 统计字母区间
            if s[i] not in map.keys():
                map[s[i]] = [i, i]
            else:
                map[s[i]][1] = i
        result = []
        processed_length = 0
        pointer = list(map.values())[0][1]
        for i in map.values():
            if i[1] < pointer:
                continue
            else:
                if i[0] > pointer:  # 划分
                    result.append(pointer - processed_length + 1)
                    processed_length = pointer + 1
                    pointer = i[1]
                else:
                    pointer = i[1]
        result.append(pointer - processed_length + 1)
        return result

另外这个题还有一种思路，划分字符串其实只需要找到每个字符的最远的边界，划分的点就是那个能够包括之前所有字符的边界的最远的边界点。所以可以进行两次循环：第一次就是确定每个字符的最远边界，第二次循环中，如果循环的索引和当前索引的字符的最远边界相同，就是要划分的位置。

3 LeetCode56 合并区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

还是找重叠的区间，只是这次需要同时记录起始位置和结束位置。

python
from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        start = intervals[0][0]
        end = intervals[0][1]
        result = []
        for i in intervals:
            if i[0] <= end:  # 重叠
                end = max(end, i[1])
            else:  # 不重叠
                result.append([start, end])
                start = i[0]
                end = i[1]
        result.append([start, end])
        return result