LeetCode: Merge Intervals Posted on January 10, 2018July 26, 2020 by braindenny Merge Intervals Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #interval, #mergelist 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]. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/merge-intervals ## Basic Ideas: sorting ## [1, 3] ## [2, 6] ## [8, 10] ## Complexity: Time O(n*log(n)), Space O(1) class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals: return [] intervals.sort() res = [] for interval in intervals: # need to extend or already covered if res and res[-1][1] >= interval[0]: res[-1][-1] = max(res[-1][-1], interval[1]) else: # empty or seperated res.append(interval) return res Post Views: 5