1.Description

Given a collection of intervals, merge all overlapping intervals.

For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. Given a collection of intervals, merge all overlapping intervals.

For example,  Given [1,3],[2,6],[8,10],[15,18],  return [1,6],[8,10],[15,18]. https://leetcode.com/problems/merge-intervals/#/description 解读 给定一些间隔（interval），合并重复的区间

2.Solution

把其中的.end和.start分别换成[-1],[0]可以在自己的IDE上进行调试

有两种思路：1）按照end进行排序；2）按照start进行排序

2.1按照end进行排序

# 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]         """         end = float('-inf')         result = []         for interval in sorted(intervals, key=lambda interval: interval.end): #如果当前区间的左界大于上次的end值，那么判断该区间的左界跟result中栈顶间隔的左界大小             if interval.start <= end: #如果小于，那说明当前间隔包含了result的栈顶间隔，把栈顶间隔弹出，                 while result[-1].start>interval.start:                     result.pop()                     if result==[] or result[-1].end<interval.start:                         result.append(interval)                         break                 result[-1].end = interval.end             else:                 result.append(interval)  # 如果没有重叠，那么就把当前的interval添加到结果中             end = interval.end         return result

2.2按照strat进行排序

class Solution(object): def merge(self, intervals): result = [] for interval in sorted(intervals, key=lambda interval: interval.start): if result and interval.start <= result[-1].end:#说明有重叠的部分 result[-1].end = max(result[-1].end, interval.end)#修改栈顶元素的右界值 else: result += interval, return result