# LC 56 Merge intervals

Given a collection of intervals, merge all overlapping intervals.

# Ideas

We first need to sort the given intervals based on the starting position.
Then there will be 3 scenarios:

1. Contain
2. Intersect
3. Non-intersect

We use an aux array called res ** to hold all the intervals that have been processed. Every intervals in **res except the last one, is finished and is in the right order.

We first start with res = [intervals] and then iterate from intervals to intervals[-1].
For interval[i]:

1. if res[-1] contains interval[i], do nothing
2. If res[-1] intersect interval[i], update res[i]’s end
3. If non intersect, append interval[i] to res.
``````    def merge(self, intervals: 'List[Interval]') -> 'List[Interval]':
#first sort based on the first index
intervals = sorted(intervals, key=lambda x: x.start)

if not intervals:return []
res = [intervals]
for i in range(1, len(intervals)):
cur_left = res[-1].start
cur_right = res[-1].end
if cur_right >= intervals[i].end: #contain
pass
elif intervals[i].start <= cur_right <= intervals[i].end:
res[-1].end = intervals[i].end
else:
res.append(intervals[i])

return res
``````

# Bugs

## Intersection occurs when intervals[i].start == res[-1].end as well

Posted on Categories Leetcode