Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

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_intervals = []
        for interval in intervals:
            # If the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged_intervals or interval[0] > merged_intervals[-1][1]:
                merged_intervals.append(interval)
            else:
                # Otherwise, there is overlap, so we merge the current and previous
                # intervals.
                merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1])

        return merged_intervals

Naive Solution

A naive approach to solving this problem involves iterating through all possible pairs of intervals and merging them if they overlap. This process is repeated until no more intervals can be merged. While this approach is straightforward, it's inefficient due to its high time complexity.

def merge_naive(intervals):
    merged = False
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            if intervals[i][1] >= intervals[j][0] and intervals[j][1] >= intervals[i][0]:
                # Overlap found, merge intervals
                intervals[i] = [min(intervals[i][0], intervals[j][0]), max(intervals[i][1], intervals[j][1])]
                del intervals[j]
                merged = True
                break  # Restart the inner loop since intervals changed
        if merged:
            merged = False
            break  # Restart the outer loop
    return intervals

Optimal Solution

The optimal solution involves sorting the intervals based on their start times and then iterating through the sorted intervals to merge overlapping intervals. This approach ensures that we only need to iterate through the intervals once, resulting in a more efficient solution.

def merge_optimal(intervals):
    intervals.sort(key=lambda x: x[0])  # Sort by start time
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

Big(O) Run-time Analysis

• Optimal Solution: The dominant operation is sorting the intervals, which takes O(n log n) time, where n is the number of intervals. The subsequent merging process takes O(n) time. Therefore, the overall run-time complexity is O(n log n).
• Naive Solution: In the worst case, where many intervals overlap, the algorithm may need to iterate through all possible pairs of intervals multiple times, resulting in a time complexity of O(n^2) or higher.

Big(O) Space Usage Analysis

• Optimal Solution: The space complexity is O(n) in the worst case, where n is the number of intervals. This is because, in the worst-case scenario, none of the intervals overlap, and we need to store all n intervals in the merged list.
• Naive Solution: The space complexity is O(1) because the algorithm modifies the input list in place and does not use any additional data structures that scale with the input size.

Edge Cases

• Empty Input: If the input list of intervals is empty, the function should return an empty list. This is a base case that needs to be handled to avoid errors.
• Non-Overlapping Intervals: If the input list contains intervals that do not overlap, the function should return the original list of intervals.
• Overlapping Intervals: If the input list contains intervals that overlap, the function should merge them correctly to produce a list of non-overlapping intervals.
• Intervals with Same Start Time: If the input list contains intervals with the same start time, the function should merge them correctly based on their end times.
• Large Number of Intervals: The function should be able to handle a large number of intervals efficiently without exceeding memory limits or execution time limits.