< Back




56. Merge Intervals

We're given an array of intervals of the form [[start_0, end_0] ... [start_n, end_n]] and we're
asked to merge overlapping intervals. We can do this pretty easily by first sorting by start time,
and then iterating through the sorted list. We maintain an answer array, if it's empty we add the
interval. Otherwise, if the start time is after the most recent added interval's end time, we just
append the interval to the answer. If the start time is before the most recent added interval's
end time, we take the max of the two intervals end time, effectively merging them, and updating the
interval at the end of the list.

The solution is as follows:


  class Solution:
      def merge(self, intervals: List[List[int]]) -> List[List[int]]:
          intervals.sort()
          ans = []

          for start, end in intervals:
              if not ans or ans[-1][1] < start:
                  ans.append([start, end])
              else:
                  ans[-1][1] = max(ans[-1][1], end)

          return ans


_ Time Complexity:

  O(nlogn) - We sort the input.

_ Space Complexity:

  O(n) - Python sorting requires O(n) space.