Python - Merge Overlapping Intervals in an Array

Python – Merge Overlapping Intervals in an Array

Merging overlapping intervals is a common problem in data structures and algorithms (DSA) interviews. In this tutorial, we will explain the problem, show sample input/output, outline the solution steps, and provide a Python program to merge overlapping intervals.

Problem Statement

Given an array of intervals where each interval is represented as a list of two integers [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sample Input and Output

Example 1:

</>

Copy

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

# Expected Output
# After merging, the intervals become:
# [[1, 6], [8, 10], [15, 18]]

Example 2:

</>

Copy

# Sample Input
intervals = [[1, 4], [4, 5]]

# Expected Output
# After merging, the intervals become:
# [[1, 5]]

Solution Approach

To solve this problem, follow these steps:

Sort the Intervals: Begin by sorting the list of intervals based on their start values. This makes it easier to compare overlapping intervals.
Initialize a Result List: Create an empty list to store the merged intervals.
Iterate through Each Interval: For each interval:
1. If the result list is empty or the current interval does not overlap with the last interval in the result, append it to the result list.
2. If there is an overlap, merge the intervals by updating the end value of the last interval in the result to be the maximum of its current end value and the end value of the current interval.
Return the Result: After processing all intervals, return the merged result list.

Python Program

The following Python program implements the above approach:

</>

Copy

def merge_intervals(intervals):
    # If the list is empty, return an empty list
    if not intervals:
        return []

    # Sort the intervals based on the start values
    intervals.sort(key=lambda x: x[0])
    
    # Initialize the result list with the first interval
    merged = [intervals[0]]
    
    # Iterate through the intervals
    for current in intervals[1:]:
        last = merged[-1]
        # If the current interval overlaps with the last merged interval, merge them
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    return merged

# Test the function with Example 1
intervals1 = [[1, 3], [2, 6], [8, 10], [15, 18]]
print("Merged Intervals Example 1:", merge_intervals(intervals1))

# Test the function with Example 2
intervals2 = [[1, 4], [4, 5]]
print("Merged Intervals Example 2:", merge_intervals(intervals2))

Output:

Merged Intervals Example 1: [[1, 6], [8, 10], [15, 18]]
Merged Intervals Example 2: [[1, 5]]

This program sorts the intervals and then iteratively merges overlapping intervals using a simple two-step comparison process.

Conclusion

In this tutorial, we covered the problem of merging overlapping intervals. We discussed the problem statement, provided sample inputs/outputs, explained the solution steps, and implemented a Python program to solve the problem.

TutorialKart

Python – Merge Overlapping Intervals in an Array