# Merge Intervals from leetcode [closed]

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

• There's at least two syntax errors and an AttributeError being thrown. Are you sure you meant to comment out the Interval class definition? Dec 29, 2017 at 10:20
• @Coal_, problem with AttributeError is PEP 3113 and python version diffrence Dec 30, 2017 at 20:30
• No, the AttributeError's to do with the fact that you commented out the Interval class definition. Dec 30, 2017 at 22:59

## 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 <= i2_l
• pattern while i < 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 > result[-1].end:
result.append(cur)
elif result[-1].end < cur.end:
result[-1].end = cur.end
return result