Merge Intervals from leetcode 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 &gt;= i2_l and i1_r &lt;= i2_r:
                    return True
                elif i2_r &gt;= i1_l and i2_r &lt;= 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 &lt; len(intervals):
                max_l, max_r = intervals[i] 
                while i &lt; 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 &lt; len(intervals) and intervals[i] == [max_l, max_r]:
                    i += 1
            return result
Python2 / Python3

Your code don't working under python 3 (PEP 3113). If possible better use newer python :).

Algorithm


no needs to change Interval to list with two elements. It's bad practise. You try low-level optimizations, not algorithm one. Code is less readable.
local functions is_intersect and merge_interval don't use knowledge that we have sorted intervals, e.g. i1_l &lt;= i2_l
pattern while i &lt; len(my_list): better change to for element in my_list: because we don't need index


Reduced code

class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution(object):
    def merge(self, intervals_struct):
        if not intervals_struct:
            return []
        intervals = sorted(intervals_struct, key=lambda x: x.start)

        result = [intervals[0]]
        for cur in intervals:
            if cur.start &gt; result[-1].end:
                result.append(cur)
            elif result[-1].end &lt; cur.end:
                result[-1].end = cur.end
        return result