Leetcode: Merge intervals

Given an array of intervals of the form [start, end], merge all overlapping intervals and return an array of non-overlapping intervals. One example is the following array [[1,2], [3,4]]. There is no overlap here. Hence the result is the same as the input. Another example is [[1,2], [1,4]]. They are overlapping and the result is [[1,4]]. If the start number of the next element is the same as the end number of the previous element, the items should be treated as overlapping. One possible solution is to first sort the items by start element. This can be achieved with an in-place sorting and a lambda expression: intervals.sort(key=lambda item: item[0]). After this, we can save the first element as the result immediately. Then we can iterate over the second to the last element and always compare the start time of the next element with the start time of the previous element. If it is equal or less then we can consider it to be overlapping and need to change the element to the maximum of both end elements. In all other cases there is no overlap and we add the whole item as is to the end of the result list.

from typing import List

class Solution:
  def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    # Sort in-place by start of interval
    intervals.sort(key=lambda item: item[0])

    res = [intervals[0]]

    for i in range(1, len(intervals)):
      if intervals[i][0] <= res[-1][1]:
        res[-1][1] = max(res[-1][1], intervals[i][1])
      else:
        res.append(intervals[i])

    return res


if __name__ == '__main__':
  s = Solution().merge
  print(s([[1,3],[2,6],[8,10],[15,18]]), [[1,6],[8,10],[15,18]])
  print(s([[1,4],[4,5]]), [[1,5]])
  print(s([[1,2]]), [[1,2]])
  print(s([[1,2], [3,4]]), [[1,2], [3,4]])
  print(s([[1,4], [0,4]]), [[0,4]])
  print(s([[1,4], [0,0]]), [[0,0], [1,4]])

Runtime: 204 ms, faster than 65.06% of Python3 online submissions for Merge Intervals. Memory Usage: 18 MB, less than 85.11% of Python3 online submissions for Merge Intervals.