Description
https://leetcode.com/problems/merge-intervals/
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Explanation
base on start and end to merge interval
Python Solution
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
result = []
intervals = sorted(intervals, key=lambda interval:interval[0])
for interval in intervals:
if len(result) == 0 or result[-1][1] < interval[0]:
result.append(interval)
else:
result[-1][1] = max(result[-1][1], interval[1])
return result
- Time complexity: ~ N
- Space complexity: ~1
One Thought to “LeetCode 56. Merge Intervals”