Merge Intervals medium

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge overlapping intervals. An interval is a pair of integers representing the start and end of an interval. You must return the merged intervals in sorted order.

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] overlaps, 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.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This makes it easier to identify overlapping intervals.

2. Initialize the merged intervals list: Create an empty list to store the merged intervals.

3. Iterate through the sorted intervals:

   • For each interval, compare it with the last interval added to the merged intervals list.
   • If there's an overlap (current interval's start is less than or equal to the last merged interval's end), merge them: update the last merged interval's end to be the maximum of the current interval's end and the last merged interval's end.
   • If there's no overlap, add the current interval to the merged intervals list.

Explanation

The core idea is to exploit the sorted nature of the intervals after sorting. If intervals are sorted, any overlap will be adjacent. We only need to compare each interval with the immediately preceding merged interval to detect and handle overlaps efficiently.

Code

def merge(intervals):
    """
    Merges overlapping intervals.

    Args:
        intervals: A list of lists, where each inner list represents an interval [start, end].

    Returns:
        A list of lists representing the merged intervals.
    """

    if not intervals:  #Handle empty input
        return []

    intervals.sort()  #Sort by start time
    merged = [intervals[0]]  #Initialize with the first interval

    for i in range(1, len(intervals)):
        current_interval = intervals[i]
        last_merged_interval = merged[-1]

        if current_interval[0] <= last_merged_interval[1]:  #Overlap
            merged[-1][1] = max(last_merged_interval[1], current_interval[1]) #Merge
        else:
            merged.append(current_interval)  #No overlap, add new interval

    return merged

Complexity

• Time Complexity: O(n log n), dominated by the sorting step. The iteration through the sorted intervals takes O(n) time.
• Space Complexity: O(n) in the worst case, if there are no overlapping intervals and the merged list is the same size as the input list. If there are many overlaps, the space complexity will be less than O(n).