56.Merge_Intervals(Medium).md

56. Merge Intervals (Medium)

Date and Time: Sep 3, 2024, 23:42 (EST)

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

Question:

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

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].

Example 2:

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= start_i <= end_i <= 10^4

Walk-through:

1. First sort intervals by the x of every interval [x, y]. So there will not exist a case [[4, 5], [15, 16], [1, 2]] and we can better hanlde the relationship between each interval.

2. For each new interval [x2, y2], we compare it with the previous interval [x1, y1]. If x2 > y1, we can append the new interval to res[], because there will not have overlap between these two intervals. Otherwise, if x2 <= y1, we can update the previous interval in res[] by taking [min(x1, x2), max(y1, y2)].

Python Solution:

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # prev: [x1, y1], interval: [x2, y2]
        # Each new interval compares with prev interval
        # If x2 > y1, res.append(interval)
        # Else, Update interval [min(x1, x2), max(y1, y2)]

        # TC: O(nlogn), n = len(intervals), SC: O(n)
        intervals.sort(key=lambda x: x[0])
        res = [intervals[0]]
        for interval in intervals:
            x1, y1 = res[-1]
            x2, y2 = interval
            if x2 > y1:
                res.append(interval)
            else:
                res[-1] = [min(x1, x2), max(y1, y2)]
        return res

Time Complexity: $O(nlog\ n)$, we sort the intervals.
Space Complexity: $O(n)$