[LeetCode]题解（python）：056-Merge Intervals

题目来源

https://leetcode.com/problems/merge-intervals/

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].

题意分析

Input:a list of intervals

Output:a list of intervals but merged

Conditions:如果两个interval有重叠，则合并

题目思路

首先对所有的intervals按照start排序，然后如果后一个interval的start在前一个interval之中，那么合并这两个interval；如果不在，则把新的interval加入

AC代码（Python）

 1 # Definition for an interval.
 2 # class Interval(object):
 3 #     def __init__(self, s=0, e=0):
 4 #         self.start = s
 5 #         self.end = e
 6 
 7 class Solution(object):
 8     def merge(self, intervals):
 9         """
10         :type intervals: List[Interval]
11         :rtype: List[Interval]
12         """
13         intervals.sort(key = lambda x:x.start)
14         length = len(intervals)
15         res = []
16         if length == 0:
17             return res
18         res.append(intervals[0])
19         for i in range(1,length):
20             size = len(res)
21             if res[size - 1].start <= intervals[i].start <= res[size - 1].end:
22                 res[size - 1].end = max(intervals[i].end, res[size - 1].end)
23             else:
24                 res.append(intervals[i])
25         
26         return res
27