56. Merge Intervals

# Question

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the original intervals.

# Solution

# Pattern

Sort and Sweep (Intervals) Sort the intervals based on their start times. Iterate through them, maintaining the "active" interval. If the next interval starts before the active one ends, extend the active interval's end time. Otherwise, finalize the active interval and start a new one.

# How to Identify

• The input is a collection of start/end pairs (events, meetings, ranges).
• The problem asks for overlapping, merging, or finding intersections.
• A brute force comparison of every interval against every other interval would be $O(N^2)$, hinting that sorting $O(N \log N)$ will unlock a linear $O(N)$ pass.

# Description

Step-by-step explanation:

1. Sort: Sort the intervals primarily by their starting times in ascending order. This guarantees that as we iterate, we will never encounter an interval that starts before the ones we've already processed.
2. Initialize: Create a dynamic List to hold our finalized intervals. Add the very first interval from our sorted array into this list. This becomes our "currently active" interval.
3. Iterate: Loop through the remaining intervals starting from index 1.
4. Compare: For each currentInterval, compare its start time to the end time of the last interval in our result list (lastMerged).
   • Overlap: If currentInterval.start <= lastMerged.end, they overlap. We merge them by updating lastMerged.end to be the maximum of lastMerged.end and currentInterval.end. (We must take the max because currentInterval could be completely engulfed by lastMerged).
   • No Overlap: If currentInterval.start > lastMerged.end, there is a gap. The lastMerged interval is completely finalized. We add currentInterval to the result list, and it now becomes the new lastMerged for future comparisons.
5. Convert: Convert the dynamic List back into a 2D integer array and return.

# The Intuition

Imagine painting lines on a ruler. If the lines are given to you in random order, it's very hard to know if a new line connects to an old one without checking every single line you've already painted. But, if you sort the instructions so that you always paint starting from the left side of the ruler moving right, you only ever need to look at the very last stroke your paintbrush made. If the new instruction says "start painting at 5cm", and your brush just lifted off the ruler at 7cm, you know they overlap, so you just keep dragging the brush to the right. If the new instruction says "start at 10cm", there is a gap, so you finalize the old line and start a brand new one.

# Complexity

# Time Complexity

Sorting the array of intervals takes $O(N \log N)$ time. The subsequent linear sweep touches each interval exactly once, taking $O(N)$ time. The sorting step dominates the asymptotic complexity.

# Space Complexity

The returned array/list requires $O(N)$ space to store the merged intervals. Additionally, the sorting algorithm itself requires $O(\log N)$ (or $O(N)$ depending on language implementation) auxiliary stack space. Overall space complexity is $O(N)$.

# Code

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
 
        // Sort intervals by their start times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
 
        List&lt;int[]&gt; merged = new ArrayList<>();
        
        // Initialize the list with the first interval
        merged.add(intervals[0]);
 
        for (int i = 1; i &lt; intervals.length; i++) {
            int[] currentInterval = intervals[i];
            // Get the last merged interval's reference
            int[] lastMerged = merged.get(merged.size() - 1);
 
            // If the current interval overlaps with the last merged one, extend the end
            if (currentInterval[0] <= lastMerged[1]) {
                lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]);
            } else {
                // No overlap, add the current interval as a new independent interval
                merged.add(currentInterval);
            }
        }
 
        return merged.toArray(new int[merged.size()][]);
    }
}

# Caveats

• Complete Subsumption: A common mistake is to write lastMerged[1] = current[1] when an overlap is found. This fails if lastMerged = [1, 10] and current = [2, 5]. The Math.max() is mathematically required because the new interval might end before the active interval ends.
• Reference Mutation: In the refined code, lastMerged[1] = ... actually mutates the array sitting inside the List. This is highly efficient but requires an understanding that Java passes object references by value.

# Concepts to Think About

• Sorting Constraints: Always clarify if the start time is guaranteed to be $\le$ the end time. Usually it is, but if [10, 2] is a valid input, you must normalize the intervals before sorting.
• Data Stream: If the intervals arrive continuously in a data stream and you must query the merged intervals at any time, sorting is impossible. You would need to use a TreeMap or a specialized Interval Tree to insert and merge in $O(\log N)$ time per element.
• Connected Components: Conceptually, this problem is equivalent to finding the Connected Components in a 1D graph where edges exist between overlapping nodes.

# Logical Follow-up

Question: Given a set of non-overlapping intervals, insert a newInterval into the intervals (merge if necessary). (LeetCode 57: Insert Interval) Solution: Since the initial array is already sorted and non-overlapping, we do not need to sort ($O(N \log N)$), we can do it in $O(N)$ time. We iterate through the array.

1. If the current interval ends before newInterval starts, add the current to results.
2. If the current interval starts after newInterval ends, add newInterval to results, and then append all remaining intervals.
3. If they overlap, mutate newInterval to be [min(starts), max(ends)] and do not add it yet (wait until the overlap is finished).

Question: Given an array of meeting time intervals, return the minimum number of conference rooms required. (LeetCode 253: Meeting Rooms II) Solution: Merging intervals tells us if things overlap, but not the maximum depth of overlap. We must separate the start times and end times into two separate sorted arrays. Use a two-pointer approach: if starts[i] < ends[j], a meeting is starting before the oldest meeting ends, so we need a new room (rooms++, i++). If starts[i] >= ends[j], a meeting ended, freeing a room (rooms--, j++). Keep track of the max_rooms. Time: $O(N \log N)$. Space: $O(N)$.