Leetcode 56. Merge Intervals

Let's understand what we're being asked to do. We have a list of intervals like [[1,3], [2,6], [8,10], [15,18]] where each interval is a pair [start, end].

Our goal is to merge overlapping intervals. Two intervals overlap if one starts before or exactly when the other ends. For example, [1,3] and [2,6] overlap because 2 <= 3, so they merge into [1,6]. Similarly, [1,3] and [3,5] are considered overlapping (touching endpoints count!) and merge into [1,5].

Tracing through the example: [1,3] and [2,6] overlap → merge to [1,6]. Then [8,10] doesn't overlap with [1,6] (gap between 6 and 8), so it stays separate. Finally [15,18] is also separate.

Key constraint: Intervals can be given in any order, not necessarily sorted!

Edge cases to consider: What if all intervals overlap into one big interval? What if no intervals overlap at all? What if we have just one interval? What about intervals like [1,4] and [4,5] where endpoints touch exactly?

The brute force approach would check every pair of intervals to see if they overlap, repeatedly merging overlapping pairs until no more merges are possible. For each interval, we'd scan through all other intervals to find overlaps, merge them, and repeat this process until a full pass produces no merges. This approach is inefficient because it requires multiple passes through the data and doesn't take advantage of any ordering.

If we process intervals in sorted order by start time, we can make a simple decision: does the current interval overlap with the previous merged interval?

Two intervals [a,b] and [c,d] overlap if c <= b (the second starts before or when the first ends). When they overlap, the merged interval is [a, max(b,d)].

By sorting first, we transform a complex problem (checking all pairs of intervals) into a single linear pass.

Once sorted, we only need to compare each interval with the most recent merged interval - we never need to look back at earlier intervals because they're guaranteed to be too far left to overlap.

Imagine scheduling meeting rooms. If you sort meetings by start time, you can process them in order:

• Start with the first meeting as your 'current block'
• For each new meeting, check: does it start before the current block ends?
• If yes, extend the current block to include it (merge)
• If no, the current block is complete - start a new block

This sweep line approach (moving left to right through sorted data) is a fundamental pattern for interval problems.

The optimal approach first sorts intervals by their start time, then makes a single pass through the sorted list. Maintain a 'current merged interval' starting with the first interval. For each subsequent interval, check if it overlaps with the current merged interval (current start <= current end). If it overlaps, extend the current interval's end to the maximum of both ends. If it doesn't overlap, add the current interval to the result and start a new current interval. This single-pass approach after sorting achieves optimal time complexity.

def merge_intervals(intervals):
    """
    Merge all overlapping intervals into minimal non-overlapping set.
    Sort by start time, then sweep through merging adjacent ranges.
    """
    # Handle empty input
    if not intervals:
        return []
    
    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])
    
    # Initialize result with first interval
    merged = [intervals[0]]
    
    # Sweep through sorted intervals
    for i in range(1, len(intervals)):
        current_interval = intervals[i]
        last_merged = merged[-1]
        
        # Check if current overlaps with last merged interval
        if current_interval[0] <= last_merged[1]:
            # Overlapping: extend the end of last merged interval
            last_merged[1] = max(last_merged[1], current_interval[1])
        else:
            # Non-overlapping: add current interval to result
            merged.append(current_interval)
    
    return merged

• Sort-then-sweep pattern: When dealing with interval problems, sorting by start time transforms a complex overlap detection problem into a simple linear scan - you only need to compare each interval with the previous merged one, not all intervals against each other.
• Greedy merging strategy: Track the current merged interval's end boundary; if the next interval's start is ≤ current end, extend the end to max(current end, next end) - this greedy approach works because sorting guarantees no earlier interval can overlap with future ones.
• Boundary condition precision: Intervals are overlapping when `next.start <= current.end` (not just `<`) because touching endpoints like [1,3] and [3,5] should merge into [1,5] - missing the equality is a common bug that leaves adjacent intervals unmerged.
• In-place vs new array tradeoff: Building a new result array is cleaner than modifying the input in-place; the O(n) space cost is acceptable and avoids complex index manipulation when merging multiple consecutive intervals.
• Time complexity insight: O(n log n) sorting dominates the O(n) merging pass, making this approach optimal for the general case - you cannot do better than O(n log n) without additional constraints because you must examine all interval relationships.
• Calendar and scheduling applications: This pattern directly applies to meeting room scheduling, resource allocation, and time-slot booking systems where you need to find free slots or detect conflicts by consolidating occupied time ranges.