Given a collection of intervals, merge all overlapping intervals.
input: [1,3],[2,6],[8,10],[15,18],
output: [1,6],[8,10],[15,18].
The logic is very simple: just merge all the intervals iteratively from first to last.
# 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_struct): """ :type intervals: List[Interval] :rtype: List[Interval] """ def is_intersect((i1_l, i1_r), (i2_l, i2_r)): if i1_r >= i2_l and i1_r <= i2_r: return True elif i2_r >= i1_l and i2_r <= i1_r: return True return False def merge_interval((i1_l, i1_r), (i2_l, i2_r)): return [min(i1_l, i2_l), max(i1_r, i2_r)] intervals = [] for i in intervals_struct: intervals.append([i.start, i.end]) intervals = sorted(intervals, key=lambda x:x[0]) i, result = 0, [] while i < len(intervals): max_l, max_r = intervals[i] while i < len(intervals) and is_intersect([max_l, max_r], intervals[i]): max_l, max_r = merge_interval([max_l, max_r], intervals[i]) i += 1 result.append([max_l, max_r]) if i < len(intervals) and intervals[i] == [max_l, max_r]: i += 1 return result