56 Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given
[1,3],[2,6],[8,10],[15,18],
return[1,6],[8,10],[15,18].The Idea: We can sort the intervals by start time, the intervals would fall under one of three cases which are illustrated below. In the first case, there are no updates. In the second case, the interval end updates, and in the third case, we add the previous interval and update the current interval.
Complexity: O(nlogn + n) time and O(1) space
class Interval:
def __init__(self, s=0, e=0):
self.start = s
self.end = e
class Solution:
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
if not intervals:
return []
intervals.sort(key=lambda i: i.start)
merged_intervals = []
cur_start = intervals[0].start
cur_end = intervals[0].end
for i, interval in enumerate(intervals[1:], 1):
if cur_start <= interval.start <= cur_end and \
cur_start <= interval.end <= cur_end:
continue
if cur_start <= interval.start <= cur_end:
cur_end = interval.end
else:
merged_intervals.append(Interval(cur_start, cur_end))
cur_start = interval.start
cur_end = interval.end
merged_intervals.append(Interval(cur_start, cur_end))
return merged_intervals
def print_intervals(intervals):
for i in intervals:
print('(', i.start, i. end, ')', end='')
print('\n')
obj = Solution()
print_intervals(obj.merge([Interval(1, 4), Interval(2, 3)])) # ( 1 4 )
print_intervals(obj.merge([])) # ( )
print_intervals(obj.merge([Interval(5, 10)])) # ( 5 10 )
print_intervals(obj.merge([Interval(1, 3), Interval(2, 10), Interval(8, 15)])) # ( 1 15 )
print_intervals(obj.merge([Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15, 18)])) # ( 1 6 )( 8 10 )( 15 18 )
print_intervals(obj.merge([Interval(1, 3), Interval(4, 6), Interval(7, 10)])) # ( 1 3 )( 4 6 )( 7 10 )