56. Merge Intervals

Solution 1: Sort

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ansIntvls = []
        intervals.sort(key=lambda intvl: intvl[0]) # Sort by start
        for intvl in intervals:
            # Interval overlap, then compare & update the tail
            if ansIntvls and intvl[0] <= ansIntvls[-1][1]:
                ansIntvls[-1][1] = max(ansIntvls[-1][1], intvl[1])
            # Interval not overlap, just add the interval to ansIntervals (e.g, [8, 10] + [15, 18])
            else:
                ansIntvls.append(intvl)
        return ansIntvls

Time Complexity: O(NLog(N))
Space Complexity: O(1)

Solution 2: Tree

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/merge-intervals/discuss/21227/7-lines-easy-Python
https://blog.techbridge.cc/2020/01/16/leetcode-%E5%88%B7%E9%A1%8C-pattern-merge-intervals/
https://leetcode.com/problems/merge-intervals/discuss/355318/Fully-Explained-and-Clean-Interval-Tree-for-Facebook-Follow-Up-No-Sorting

Follow-ups

252 Meeting Rooms
253 Meeting Rooms II
435 Non-overlapping Intervals