https://leetcode.com/problems/merge-intervals/
Merge Intervals
Total Accepted: 47467 Total Submissions: 206089 Difficulty: Hard
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].
Code
# 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):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
r = []
for i in sorted(intervals, key=lambda x: x.start):
if r and i.start <= r[-1].end:
r[-1].end = max(i.end, r[-1].end)
else:
r += [i]
return r
Idea
First, sort intervals based on their start points (Achieve in O(nlogn) time). Then, one by one examining whether the current start point is behind or in front of the last effective interval’s end point. The following plot shows the specific rules for update:
