Merge Intervals

Naive Solution: Brute Force

One naive approach to merging overlapping intervals is to iterate through all possible pairs of intervals and check for overlap. If two intervals overlap, merge them and update the list of intervals. Repeat this process until no more overlaps are found.

Algorithm:

1. For each interval i in the list of intervals:
2. For each interval j in the list of intervals (where j != i):
3. Check if intervals i and j overlap.
4. If they overlap, merge them into a new interval.
5. Replace intervals i and j with the new merged interval and remove the old intervals.
6. Repeat steps 1-5 until no more overlaps are found.

Time Complexity: O(n^3) in the worst case, where n is the number of intervals. This is because for each interval, we iterate through all other intervals, and in the worst case, we might have to repeat this process multiple times.

Space Complexity: O(1) if we modify the input list in place. Otherwise, O(n) if we create a new list to store the merged intervals.

This approach is inefficient and not recommended for large inputs.

Optimal Solution: Sorting and Merging

A more efficient approach involves sorting the intervals based on their start times. After sorting, we can iterate through the sorted intervals and merge overlapping intervals in a single pass.

Algorithm:

1. Sort the intervals based on their start times.
2. Initialize an empty list to store the merged intervals.
3. Iterate through the sorted intervals:
   • If the current interval does not overlap with the last interval in the merged list, add it to the merged list.
   • If the current interval overlaps with the last interval in the merged list, merge them into a single interval and update the last interval in the merged list.
4. Return the merged list.

Code (Python):

def merge(intervals):
    intervals.sort(key=lambda x: x[0])  # Sort by start times
    merged = []

    for interval in intervals:
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

Explanation:

1. Sorting: The intervals.sort(key=lambda x: x[0]) line sorts the input intervals in ascending order based on their start times. This is crucial for efficiently merging overlapping intervals.
2. Initialization: The merged = [] line initializes an empty list to store the merged intervals.
3. Iteration and Merging: The code iterates through each interval in the sorted intervals list. Inside the loop:
   • if not merged or interval[0] > merged[-1][1]: This condition checks if the merged list is empty or if the current interval's start time is greater than the end time of the last interval in the merged list. If either of these conditions is true, it means the current interval does not overlap with the last merged interval, so we append it to the merged list.
   • else: merged[-1][1] = max(merged[-1][1], interval[1]) If the current interval overlaps with the last interval in the merged list, we merge them by updating the end time of the last interval in the merged list to be the maximum of its current end time and the end time of the current interval.
4. Return: Finally, the function returns the merged list, which contains the non-overlapping intervals that cover all the intervals in the input.

Time Complexity: O(n log n) due to the sorting step, where n is the number of intervals. The merging step takes O(n) time.

Space Complexity: O(n) in the worst case, where n is the number of intervals. This is because in the worst case, none of the intervals overlap, and we need to store all of them in the merged list.

Edge Cases:

• Empty input: If the input list of intervals is empty, the function should return an empty list.
• Single interval: If the input list contains only one interval, the function should return a list containing that interval.
• Overlapping intervals: The function should correctly merge overlapping intervals, even if there are multiple overlapping intervals in a row.
• Non-overlapping intervals: The function should correctly handle non-overlapping intervals and return them as is.