56. Merge Intervals

Medium

Problem:

Merge the overlapping intervals.

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Input: intervals = [[1,4],[0,2],[3,5]]
Output: [[0,5]]

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

What to learn:

Comma Operator in Python

Simply using += concatenates the elements. This operation is equivalent to the matrix concatenation.

>>> a = [1]
>>> b= [2, 3]
>>> a += b
>>> a
[1, 2, 3]

The comma creates a nested list, which serves the same purpose as providing square brackets [].

>>> a = [1]
>>> b= [2, 3]
>>> a += b,
>>> a
[1, [2, 3]]

Therefore, whether using a comma or square brackets, both serve the same purpose.

Solution:

1. Sort based on the first value.

2. If the start of the current item overlaps with the end of the previous item, continue merging based on the maximum value.

3. If the start of the next item no longer overlaps with the end of the previous item, stop merging and add a new item.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        results = []
        for i in sorted(intervals, key=lambda x: x[0]):
            if results and i[0] <= results[-1][1]:
                results[-1][1] = max(results[-1][1], i[1])
            else:
                results += i,
        return results

The time complexity is O(nlogn) due to the sorting. The remaining task of traversing the list is performed in linear time.