Given a list of intervals, merge the overlaps. How do you optimize it?

To merge overlapping intervals efficiently, first sort the intervals by their start times. Then, iterate through the sorted list, merging intervals that overlap with the last merged interval. This approach yields a time complexity of O(N log N) due to the sorting step, and O(N) space complexity in the worst case for the result.

The core principle is that sorting by start time guarantees that any potential overlap for the current interval must occur with an interval that has already been processed or is the next in the sorted sequence. After initializing a result list with the first interval, we iterate through the remaining intervals:

Example:
Input: [[1,3], [2,6], [8,10], [15,18]]

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0]) # Sort by start time
    
    merged = [intervals[0]]
    for current_start, current_end in intervals[1:]:
        last_merged_end = merged[-1][1]
        
        if current_start <= last_merged_end: # Overlap
            merged[-1][1] = max(last_merged_end, current_end)
        else: # No overlap
            merged.append([current_start, current_end])
            
    return merged

In a production data engineering context, this pattern is highly relevant for tasks like consolidating time windows (e.g., event logs, sensor data validity periods, or sessionization) or merging data ranges within a data warehouse. For extremely large datasets that don't fit in memory, the sorting step becomes the primary challenge. Distributed processing frameworks like Apache Spark would require a distributed sort (e.g., using sortBy or sortByKey, which involves shuffles across partitions) before a linear scan can be performed. If intervals are already naturally grouped by a key (e.g., customer ID or device ID), then merging can occur independently within each group after a groupBy operation, significantly reducing the global sorting overhead.

In the interview, also mention handling edge cases like an empty input list or a list with a single interval.