leetcode56-- Merge Intervals (合并无序区间)

leetcode56-- Merge Intervals (合并无序区间)

题目

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.


这个题目的意思是给了一些无序的区间, 这些区间有些可能有overlap,所以可以进行整合,结果要返回不能够再进行整合的区间的集合。

解法是先将区间按照第一个元素进行排个序,然后再根据排好序的遍历一次就可以了。 解法如下


# 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]
        """
        
        if len(intervals)==0:
            return []
        
        intervals = sorted(intervals, key=lambda x: x.start)
        
        ret = [intervals[0]]
        
        for x in intervals[1:]:
            if ret[-1].end < x.start:   # 只有这样的时候不会合并
                ret.append(x)
            else:
                ret[-1].end = max(ret[-1].end, x.end)
                
        return ret

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦