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

题目来源：

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

---

题意分析：

　　给定一连串的间隔，将有交叉的间隔整合起来。比如：给出[[1,3],[2,4]]那么应该返回[[1,4]]。要注意的是类似[[1,2],[2,3]]也要整合成[[1,3]]。

---

题目思路：

　　首先将间隔排序，接着从头开始，如果发现前一个的最后不小于后一个的第一个，那么将这两个整合成一个新的间隔。也就是if tmp.end <= intervals[i].start: tmp.end = max(tmp.end,intervals[i].end)。

---

代码（python）：

　　

# 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]
        """
        intervals.sort(key = lambda interval : interval.start)
        ans,size = [],len(intervals)
        if size == 0:
            return ans
        tmp = intervals[0]
        for i in intervals:
            if i.start <= tmp.end:
                tmp.end = max(i.end,tmp.end)
            else:
                ans.append(tmp)
                tmp = i
        ans.append(tmp)
        return ans

---

转载请注明出处：http://www.cnblogs.com/chruny/p/4969074.html