Merge Intervals

December 21, 2023

Problem #

Given a list of intervals (each interval represented by a pair of integers), merge overlapping intervals and return the result in sorted order.

Solution #

The Python function merge_intervals successfully merges overlapping intervals and returns the result in sorted order. Here’s the code:

def merge_intervals(intervals):
    """
    Merge overlapping intervals and return the result in sorted order.

    :param intervals: A list of intervals, each represented as a pair of integers
    :return: A list of merged intervals in sorted order
    """
    # Sort the intervals based on the starting value of each interval
    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 previous
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Otherwise, there is an overlap, so we merge the current and previous intervals
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

# Example usage
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
merged_intervals = merge_intervals(intervals)
print(merged_intervals)

This code works as follows:

• First, it sorts the intervals based on the starting value of each interval.
• Then, it iterates through the sorted intervals. For each interval, it checks if it overlaps with the last interval in the merged list.
• If there’s no overlap, the interval is added to merged. If there is an overlap, it merges the current interval with the last one in merged by updating the end value of the last interval in merged to be the maximum of its own end and the end of the current interval.
• The resulting merged list contains the merged intervals in sorted order.

In the provided example, intervals [[1, 3], [2, 6], [8, 10], [15, 18]] are merged into [[1, 6], [8, 10], [15, 18]].

Solution analysis #

The algorithm used in the provided code for merging intervals is a combination of sorting and a linear scan. This approach is commonly used in interval problems and is known for its efficiency and simplicity. Here’s how it works:

Sorting #

• Initial Step: The algorithm starts by sorting the list of intervals based on their starting points. This is crucial because it arranges the intervals in a sequence where checking for overlaps becomes straightforward.
• Sorting Criterion: The key for sorting is the starting point of each interval (lambda x: x[0]), ensuring that intervals with lower start points come first.

Linear Scan #

• One Pass Through Sorted Intervals: After sorting, the algorithm makes a single pass through the sorted intervals.
• Merging Logic:
  • No Overlap: If the current interval (interval) does not overlap with the last interval in the merged list, it is added to merged. This is determined by checking if the start of the current interval is greater than the end of the last interval in merged.
  • Overlap: If there is an overlap, the algorithm merges the current interval with the last interval in merged. This is done by updating the end of the last interval in merged to the maximum end value between the two overlapping intervals.

Efficiency #

• Time Complexity: The time complexity of this algorithm is dominated by the sorting step, which is typically O(n log n) for n intervals. The linear scan is O(n), making the overall time complexity O(n log n).
• Space Complexity: The space complexity is O(1) or O(n), depending on whether the sorting algorithm used is in-place. In the Python implementation provided, the sort is in-place, and the additional space used is for the merged list.

Algorithm Usage #

This algorithm is widely used in problems involving intervals, such as calendar scheduling, meeting rooms, and interval partitioning, due to its effectiveness in handling overlapping intervals with a sorted order.