Merge Intervals

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

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort the intervals based on the start time
        intervals.sort(key=lambda x: x[0])
        
        merged = []
        for interval in intervals:
            # If the list of merged intervals is empty or if the current
            # interval does not overlap with the last interval, simply append it.
            if not merged or interval[0] > merged[-1][1]:
                merged.append(interval)
            else:
                # Otherwise, there is overlap, so we merge the current interval
                # with the last interval.
                merged[-1][1] = max(merged[-1][1], interval[1])
                
        return merged

Explanation:

The problem requires merging overlapping intervals. The approach involves sorting the intervals by their start times and then iterating through the sorted intervals. For each interval, we check if it overlaps with the last merged interval. If it does, we merge them; otherwise, we add the current interval to the merged list.

1. Sort Intervals: The intervals list is sorted based on the start time of each interval.
2. Iterate Through Intervals: The code iterates through each interval in the sorted list.
3. Check for Overlap:
   • If the merged list is empty or the current interval's start time is greater than the end time of the last interval in the merged list, then there is no overlap. The current interval is appended to the merged list.
   • Otherwise, there is an overlap. The end time of the last interval in the merged list is updated to be the maximum of its current end time and the end time of the current interval.

Example:

Consider the input intervals = [[1,3],[2,6],[8,10],[15,18]]:

1. Sort: The intervals are already sorted: [[1,3],[2,6],[8,10],[15,18]].
2. Iterate:
   • [1,3] is added to merged. merged = [[1,3]].
   • [2,6] overlaps with [1,3]. merged[-1][1] becomes max(3,6) = 6. merged = [[1,6]].
   • [8,10] does not overlap with [1,6]. merged = [[1,6],[8,10]].
   • [15,18] does not overlap with [8,10]. merged = [[1,6],[8,10],[15,18]].

Consider the input intervals = [[1,4],[4,5]]:

1. Sort: The intervals are already sorted: [[1,4],[4,5]].
2. Iterate:
   • [1,4] is added to merged. merged = [[1,4]].
   • [4,5] overlaps with [1,4]. merged[-1][1] becomes max(4,5) = 5. merged = [[1,5]].

Edge Cases:

1. Empty Input: If the input intervals is empty, the function should return an empty list.
2. Single Interval: If the input contains only one interval, the function should return a list containing that interval.
3. Non-Overlapping Intervals: If the input intervals do not overlap, the function should return the sorted list of intervals.
4. Overlapping and Non-Overlapping Intervals: The function correctly handles cases where there is a mix of overlapping and non-overlapping intervals.
5. Intervals with Same Start Time: The function correctly merges intervals that have the same start time but different end times.

Big O Runtime Analysis:

• Sorting: The sort method takes O(n log n) time, where n is the number of intervals.
• Iteration: The for loop iterates through each interval once, which takes O(n) time.

Therefore, the overall time complexity is O(n log n), dominated by the sorting step.

Big O Space Usage Analysis:

• Merged List: In the worst case, if no intervals overlap, the merged list will contain all n intervals. This takes O(n) space.

Therefore, the overall space complexity is O(n).