day36| 435+763+56-526互联

435. 无重叠区间

题目简述：

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

思路：

利用昨天题目452的思路即可

代码：

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)

        intervals.sort(key=lambda intervals:(intervals[1],intervals[0]))

        delete_num=0
        pos=intervals[0][1]

        for interval in intervals:
            if interval[0]>=pos:
                pos=interval[1]
            else:
                delete_num+=1

        return delete_num-1

763. 划分字母区间

题目简述：

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

思路：

1. 首先用collections模块里面的Counter()记录每个字符出现的次数:
　　c=collections.Counter(s)

2. 再创建一个字典dict

3. 从左至右遍历字符串。遇到dict里面没有的，加进dict，dict里面有的，对应char的
　　dict['char']+=1

4. 如果dict['char']==c['char']，说明所有的char都出现了，往后不用担心会出现char影响我们划分了

5. 如果此时dict里面还没有任何一个键值对，那么就说明遍历至此，刚好是一个分组

6. 就假如dict只出现过 a,b,c ，那么dict为说明字符串中的a,b,c都被我们遍历过了

代码如下：

import collections
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        dict={}
        res=[]
        num=0
        c=collections.Counter(s)

        for j in s:

            if j not in dict.keys():
                dict[j]=1
                num+=1
            else:
                dict[j]+=1
                num+=1
            
            if dict[j]==c[j]:
                del dict[j]
                if len(dict)==0:
                    res.append(num)
                    num=0
        
        return res

56. 合并区间

题目简述：

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

思路：

还是利用昨天452的思路，先排序，然后分类讨论

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 首先是排序
        intervals.sort(key=lambda intervals:(intervals[0],intervals[1]))
        res=[]
        left=intervals[0][0]
        right=intervals[0][1]

        for interval in intervals:
            if right>=interval[0] and right<=interval[1]:
                right=interval[1]
                if left>=interval[0]:
                    left=interval[0]
            elif right>=interval[0] and right>=interval[1]:
                continue
            else:
                res.append([left,right])
                left=interval[0]
                right=interval[1]
        res.append([left,right])
        return res

总结：

先排序，再处理可以解决很多问题