leetcode 重叠区间问题

重叠区间问题可以总结为在坐标轴上若干个位置为 (start(i),end(i))的区间，要求求解这些区间中有多少个不重叠区间，或者合并重叠的区间。

leetcode有大神总结了通用模板，点这里 

该问题分两类：第一类求重叠区间个数（leetcode 452，435），第二类求合并后的区间（leetcode 56，763）。

对于第一类问题，通常按照end排序，维护一个end变量即可。

低于第二类问题，通常按照start排序，维护一个数组，每次取最后一个数作为比较的标准。

注意按照start或者end排序两种方式都可以求解，只是在不同情况下用其中之一代码编写更简洁。

本文总结了leetcode中重叠区间问题的题目，涉及到的题目如下：

leetcode 56 合并区间

leetcode 452 射气球

leetcode 435 无重叠区间

leetcode 763 划分字母区间

452 

题目描述：每个坐标表示气球存在的区间，要求用最少的箭（射箭方向垂直坐标轴 ）射完所有的气球。

1

2

3

4

5

6

7

8

9

10

11

12

def findMinArrowShots(self, points):

    """

    :type points: List[List[int]]

    :rtype: int

    """        # 按照end排序，更推荐的方法

    res=0

    end=float('-inf')

    for p in sorted(points,key=lambda x: x[1]):

        if p[0]>end:

            res+=1

            end=p[1]

    return res

1

2

3

4

5

6

7

8

9

10

11

12

def findMinArrowShots(self, points):

    """

    :type points: List[List[int]]

    :rtype: int

    """

    # 按照start排序

    res,shoot=0,float('inf')

    for s,e in sorted(points,reverse=True):

        if shoot>e:

            res+=1

            shoot=s

    return res

435

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

示例 1:

示例 2:

示例 3:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

def eraseOverlapIntervals(self, intervals):

    """

    :type intervals: List[Interval]

    :rtype: int

    """

    ans = 0

    end = float('-inf')

    for p in sorted(intervals,key=lambda x:x.end):

        if p.start>=end:

            end=p.end

        else:

            ans+=1

    return ans

56

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

示例 2:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for an interval.

# class Interval(object):

#     def __init__(self, s=0, e=0):

#         self.start = s

#         self.end = e

class Solution(object):

    def merge(self, intervals):

        """

        :type intervals: List[Interval]

        :rtype: List[Interval]

        """        # 按照 start排序，对于输入[[2,3],[4,5],[6,7],[8,9],[1,10]],排序后为[[1,10],[2,3],[4,5],[6,7],[8,9]],只需要取ans最后一个数比较

        ans=[]

        for p in sorted(intervals,key=lambda x: x.start):

            if ans and p.startd[0]:

            ans[-1][1] = max(ans[-1][1],d[1])

        else:

            ans.append(d)

    return [d[1]-d[0]+1 for d in ans]