题目来源
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
[LeetCode]题解（python）：056-Merge Intervals
原文：http://www.cnblogs.com/loadofleaf/p/5084209.html