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:
- Contain
- Intersect
- 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[0]] and then iterate from intervals[1] to intervals[-1].
For interval[i]:
- if res[-1] contains interval[i], do nothing
- If res[-1] intersect interval[i], update res[i]’s end
- 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[0]]
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