Merge Intervals

https://leetcode.com/problems/merge-intervals

# Solution

The brute-force solution represents graph as adjacency list.

# Sort

Note the use of lamdba function to sort by start time in sorted method.

Complexity:

  • time: O(nlogn)O(n\log n)
  • space: O(1)O(1)
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    res = []
    if not intervals: return res
    intervals = sorted(intervals, key=lambda elt : elt[0])

    for interval in intervals:
        if not res or interval[0] > res[-1][1]:
            res.append(interval)
        else:
            res[-1][1] = max(res[-1][1], interval[1])
    return res
Last Updated: 7/19/2020, 3:45:14 PM