Given a collection of intervals merge overlapping intervals in Python

 Merge Intervals: Given a collection of intervals, merge overlapping intervals Python Program?

To merge overlapping intervals, you can follow a systematic approach to combine intervals that overlap into a single interval. Here’s how you can do it in Python:

Approach

1. Sort Intervals: Start by sorting the intervals based on their starting times. This helps in easily merging overlapping intervals since overlapping intervals will be adjacent in a sorted list.

2. Merge Intervals: Iterate through the sorted intervals and merge them if they overlap. If they don’t overlap, push the current interval to the results and continue.

Detailed Solution

Here's a step-by-step implementation:

def merge_intervals(intervals):

    if not intervals:

        return []

    # Step 1: Sort the intervals by their start time

    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]  # Initialize with the first interval

    for current in intervals[1:]:

        last_merged = merged[-1]  # Get the last merged interval

        # Check if the current interval overlaps with the last merged interval

        if current[0] <= last_merged[1]:

            # Merge the intervals by updating the end time of the last merged interval

            last_merged[1] = max(last_merged[1], current[1])

        else:

            # If no overlap, add the current interval to the merged list

            merged.append(current)

    return merged

# Example usage:

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

print(merge_intervals(intervals))  # Output: [[1, 6], [8, 10], [15, 18]]

Explanation

1. Sorting: Intervals are sorted based on their starting times. Sorting is done using intervals.sort(key=lambda x: x[0]), which sorts the intervals by their start times in ascending order.

2. Merging: After sorting, iterate through the intervals. For each interval, check if it overlaps with the last interval in the merged list. If it does, update the end time of the last merged interval to the maximum end time of the overlapping intervals. If it doesn’t overlap, simply add the current interval to the merged list.

3. Handling Edge Cases: The code handles edge cases like an empty list by checking if intervals is empty at the beginning.

Complexity

• Time Complexity: $O(n \log n)$, where $n$ is the number of intervals. The sorting step dominates the time complexity.
• Space Complexity: $O(n)$ for storing the merged intervals.

This approach ensures that you efficiently merge overlapping intervals and handle various scenarios correctly.