Fork me on GitHub

Merge Intervals

Posted on

Description

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

Solution

The key point here is to sort all the intervals, then we add each interval by order to merge(insert) into the new intervals.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 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]
        """
        sorted_intervals = sorted(intervals, key=lambda x: x.start)
        if len(sorted_intervals) == 0 or len(sorted_intervals) == 1:
            return intervals
        
        ret = [ sorted_intervals[0] ]
        for index in range(1, len(sorted_intervals)):
            pre_start = ret[-1].start
            pre_end = ret[-1].end
            current_start = sorted_intervals[index].start
            current_end = sorted_intervals[index].end
            
            if pre_end < current_start:
                ret.append(Interval(current_start, current_end))
                continue
            ret.pop()
            new_start = pre_start
            new_end = max(pre_end, current_end)
            ret.append(Interval(new_start, new_end))        
                    
        return ret;