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