Mastering the Merge Intervals Pattern

The Merge Intervals pattern is a fundamental algorithmic technique used to solve problems involving ranges, segments, or intervals. These problems typically represent intervals as pairs of coordinates—a start time and an end time—and require you to merge overlapping segments, identify scheduling conflicts, or compress contiguous data ranges.

1. The Core Problem: Why Do We Need Merge Intervals?

In many real-world applications, data is not represented as discrete, isolated points, but rather as continuous blocks or ranges.

An interval is mathematically defined as:

Where:

• $S_i$ represents the start of the interval.
• $E_i$ represents the end of the interval, such that $S_i \le E_i$.

When dealing with a collection of these intervals, they frequently overlap. Without a systematic way to process them, determining relationships between ranges (such as finding free time slots in a calendar or checking for resource conflicts) becomes highly inefficient, often requiring $O(N^2)$ brute-force comparisons.

The Merge Intervals pattern provides an elegant framework to resolve these overlaps in $O(N \log N)$ time.

2. The Core Mental Model & Real-World Analogies

To build an intuitive understanding of intervals, consider how they interact in physical space and time.

Real-Life Analogy: The Shared Calendar

Imagine you are booking meeting rooms or scheduling events on a calendar:

• Meeting A: 1:00 PM to 3:00 PM ([1, 3])
• Meeting B: 2:00 PM to 6:00 PM ([2, 6])

Because Meeting B starts before Meeting A ends ($2 < 3$), these two meetings overlap. If you want to block out the total busy time on your calendar, you merge them into a single continuous block: 1:00 PM to 6:00 PM ([1, 6]).

Key Industrial Use Cases

The Merge Intervals pattern is widely applied across several domains:

• Calendar Event Merging: Consolidating busy times from multiple team members to find a mutual free slot.
• CPU Scheduling: Merging busy execution intervals to determine CPU utilization and idle times (a classic hard problem frequently asked in Google interviews).
• Data Compression: Storing large sequences of sequential data as compressed ranges (e.g., run-length encoding or database index ranges) instead of individual elements.
• Network IP Ranges: Merging overlapping IP subnets or routing tables to optimize network traffic routing.

3. The Fundamental Overlap Condition: Naive vs. Sorted Approach

To determine if two intervals, $A = [S_a, E_a]$ and $B = [S_b, E_b]$, overlap, we must compare their boundaries.

The Naive Approach (Unsorted)

If the input intervals are unsorted, any interval can overlap with any other interval in the list. To find all overlaps, you would have to compare every single interval with every other interval:

This brute-force comparison requires two nested loops, resulting in a time complexity of $O(N^2)$.

The Better Approach (Sorted)

By sorting the intervals by their start times ($S_i$), we establish a linear progression.

Crucial Insight: Overlap can only happen between intervals that are adjacent to each other after sorting.

Once sorted, if interval $B$ comes immediately after interval $A$, we know for certain that $S_b \ge S_a$. Therefore, we only need to check one condition to determine if they overlap:

If the start of the current interval ($S_b$) is less than or equal to the end of the previous interval ($E_a$), they must overlap.

4. Step-by-Step Evolution of the Merge Algorithm

When we detect an overlap between a running merged interval and a new interval, we must combine them. The evolution of this merge follows a simple mathematical rule.

Step 1: Sort

Sort all intervals in ascending order based on their start times.

Step 2: Initialize

Keep track of a "last merged interval" (or the current interval being evaluated).

Step 3: Iterate and Compare

For each subsequent interval in the sorted list:

Last Merged Interval: [S_last, E_last]
Current Interval:     [S_curr, E_curr]

• Case A: Overlap Detected ($S_{\text{curr}} \le E_{\text{last}}$) We merge the current interval into the last merged interval. The new start remains $S_{\text{last}}$ (since it is already sorted and thus smaller), but the new end becomes the maximum of the two end times:

• Case B: No Overlap ($S_{\text{curr}} > E_{\text{last}}$) The current interval is completely disjoint from the last merged interval. We append the current interval to our results and update our "last merged interval" pointer to the current interval.

5. Pattern Recognition: How to Spot Interval Problems in the Wild

To identify if a coding problem can be solved using the Merge Intervals pattern, look for specific structural clues and keywords in the problem description.

Key Indicators

• The input is explicitly described as a 2D array, a list of pairs, or ranges (e.g., [[start_1, end_1], [start_2, end_2]]).
• The problem mentions scheduling, time segments, calendar events, or resource allocation.
• You are asked to find conflicts, identify gaps, merge redundant ranges, or find the minimum resources (like meeting rooms) needed to cover all intervals.

Keyword Cheat Sheet

6. Deep Dive 1: Merge Intervals (LeetCode 56) — Problem Analysis & Visual Flow

Problem Statement

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 intervals in the input.

Visual Walkthrough

Let's trace the algorithm using the following input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

Visual Flow Diagram

7. Deep Dive 1: Implementation & Code Walkthrough

Below is the complete, production-grade Java implementation for LeetCode 56. This code uses an in-place array tracking mechanism to optimize memory allocation, matching the logic discussed in the lecture.

import java.util.Arrays;

public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        // Edge case: if there are no intervals or only one, no merging is needed
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // Step 1: Sort the intervals by their start times using a custom comparator
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int n = intervals.length;
        // Create a temporary array to store the merged intervals
        int[][] result = new int[n][2];
        
        // Initialize the first interval as the starting point
        result[0] = intervals[0];
        int e = 0; // Pointer tracking the index of the last merged interval in 'result'

        // Step 2: Iterate through the intervals starting from the second one
        for (int i = 1; i < n; i++) {
            int currentStart = intervals[i][0];
            int currentEnd = intervals[i][1];
            int lastMergedEnd = result[e][1];

            // Check if the current interval overlaps with the last merged interval
            if (currentStart <= lastMergedEnd) {
                // Overlap: Update the end time of the last merged interval to be the maximum
                result[e][1] = Math.max(lastMergedEnd, currentEnd);
            } else {
                // No overlap: Move the pointer forward and add the current interval
                e++;
                result[e] = intervals[i];
            }
        }

        // Step 3: Return only the populated portion of the result array
        // Since 'e' is a 0-based index, the number of merged intervals is 'e + 1'
        return Arrays.copyOfRange(result, 0, e + 1);
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N \log N)$
  • Sorting the $N$ intervals takes $\mathcal{O}(N \log N)$ time.
  • The single-pass linear scan to merge the intervals takes $\mathcal{O}(N)$ time.
  • Thus, the sorting step dominates the overall time complexity.
• Space Complexity: $\mathcal{O}(N)$ (or $\mathcal{O}(\log N)$ auxiliary space for sorting)
  • We allocate a result array of size $N$ to store the merged intervals.

8. Deep Dive 2: Insert Interval (LeetCode 57) — The Naive vs. Optimized $O(N)$ Approach

Problem Statement

You are given an array of non-overlapping intervals intervals sorted in ascending order by start time. You are also given a newInterval = [start, end] representing the start and end of another interval.

Insert newInterval into intervals such that the list remains sorted in ascending order and has no overlapping intervals (merge any overlapping intervals if necessary).

The Naive Approach

1. Append the newInterval to the end of the intervals array.
2. Re-sort the entire array: $\mathcal{O}(N \log N)$.
3. Run the standard merge intervals algorithm: $\mathcal{O}(N)$.

While simple, this approach is inefficient because it completely discards the valuable property that the input list is already sorted and non-overlapping.

The Optimized Approach ($\mathcal{O}(N)$ Linear Scan)

Since the input is already sorted, we can insert and merge the new interval in a single pass using a three-phase linear scan:

Phase 1: Add all intervals that end before the new interval starts.
         (No overlap, completely to the left)

Phase 2: Merge all overlapping intervals with the new interval.
         (Update start to min of starts, end to max of ends)

Phase 3: Add all remaining intervals that start after the merged interval ends.
         (No overlap, completely to the right)

Visualizing the Three Phases

Let's trace: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]

Phase 1: Left Disjoint Intervals
- Check [1, 3]: Ends at 3. New interval starts at 2. 
  Since 3 >= 2, this overlaps! Phase 1 ends.

Phase 2: Merging Overlaps
- We are at [1, 3]. It overlaps with [2, 5].
  Update newInterval:
  - Start = min(1, 2) = 1
  - End = max(3, 5) = 5
  newInterval is now [1, 5].
- Move to next interval [6, 9].
  Does [6, 9] overlap with [1, 5]?
  Start of current (6) > End of newInterval (5). No overlap. Phase 2 ends.
- Add merged [1, 5] to output.

Phase 3: Right Disjoint Intervals
- Add remaining intervals as-is: [6, 9].

Result: [[1, 5], [6, 9]]

9. Deep Dive 2: Implementation & Code Walkthrough

Here is the linear-time implementation of LeetCode 57.

import java.util.ArrayList;
import java.util.List;

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int n = intervals.length;
        int i = 0;

        // Phase 1: Add all intervals that end before the new interval starts
        // These intervals are completely to the left of the new interval and do not overlap.
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Phase 2: Merge all overlapping intervals with the new interval
        // Overlap occurs as long as the current interval's start is less than or equal to the new interval's end.
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        // Add the final merged version of the new interval
        result.add(newInterval);

        // Phase 3: Add all remaining intervals
        // These intervals are completely to the right of the merged interval.
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        // Convert the dynamic list back to a 2D array
        return result.toArray(new int[result.size()][2]);
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  • We perform a single pass over the array of size $N$. Each interval is processed exactly once.
• Space Complexity: $\mathcal{O}(N)$
  • We allocate an auxiliary list to store the output intervals.

10. Deep Dive 3: Meeting Rooms I (LeetCode 252) — Conflict Detection

Problem Statement

Given an array of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (where $s_i < e_i$), determine if a person could attend all meetings.

Core Logic

A person can attend all meetings if and only if no two meetings overlap. If even a single overlap is detected, the person cannot attend all meetings, and we must return false.

To check for overlaps:

1. Sort the meetings by their start times.
2. Iterate through the sorted meetings and compare each meeting with the one immediately preceding it.
3. If the current meeting starts before the previous meeting ends, we have a conflict.

Meeting A: [1, 3]
Meeting B: [2, 5]

Since Meeting B starts at 2, which is before Meeting A ends at 3, there is a conflict.

Note: If a meeting ends at exactly the same time another meeting starts (e.g., [1, 3] and [3, 5]), they do not overlap. A person can transition instantly from one meeting to the next. Therefore, the conflict condition is strictly:

Implementation

import java.util.Arrays;

public class MeetingRooms {
    public boolean canAttendMeetings(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return true;
        }

        // Step 1: Sort the meetings by their start times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // Step 2: Check for any overlapping adjacent meetings
        for (int i = 1; i < intervals.length; i++) {
            int currentStart = intervals[i][0];
            int previousEnd = intervals[i - 1][1];

            // If the current meeting starts before the previous one ends, there is a conflict
            if (currentStart < previousEnd) {
                return false;
            }
        }

        return true;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N \log N)$ due to the sorting step. The subsequent linear scan takes $\mathcal{O}(N)$ time.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space (or $\mathcal{O}(\log N)$ depending on the sorting algorithm's call stack).

11. Common Pitfalls, Edge Cases, and Debugging Workflows

When implementing interval-based algorithms, pay close attention to boundary conditions. These are the most common sources of bugs in coding interviews.

1. Inclusive vs. Exclusive Boundaries

Always clarify whether intervals are inclusive or exclusive at their boundaries.

• Strict Overlap: Do [1, 3] and [3, 5] overlap?
  • In Merge Intervals, we typically merge them: [1, 5]. The condition is start <= lastEnd.
  • In Meeting Rooms, they do not conflict. A person can attend both. The condition is start < lastEnd.

2. Sorting Order

Always sort by the start time (index 0), not the end time. Sorting by end times is used in other greedy algorithms (like Interval Scheduling Maximization), but for merging, sorting by start times is required to guarantee that all potentially overlapping intervals are adjacent.

3. Empty or Single Element Inputs

Always handle empty arrays or arrays with a single interval at the very beginning of your function to prevent out-of-bounds errors:

if (intervals == null || intervals.length == 0) {
    return new int[0][0];
}

4. Tracking the Merged State

When updating the end of an interval during a merge, always use Math.max(). Do not assume the current interval's end time is larger than the previous one. For example, if you merge [1, 10] and [2, 5], the merged interval is [1, 10], not [1, 5].

Correct:   result[e][1] = Math.max(result[e][1], currentEnd);
Incorrect: result[e][1] = currentEnd;

12. Summary and Key Takeaways

• The Core Objective: The Merge Intervals pattern is designed to resolve overlapping ranges in a collection of intervals by sorting and processing them sequentially.
• Sorting is Mandatory: Sorting by start times ensures that overlapping intervals are adjacent, reducing the search space from $O(N^2)$ to $O(N \log N)$.
• The Overlap Condition: Two sorted intervals $A$ and $B$ overlap if and only if $S_b \le E_a$.
• The Merging Rule: When merging two overlapping intervals, the new start time is $S_a$ (the smaller of the two), and the new end time is $\max(E_a, E_b)$.
• Linear Insertion: Inserting a new interval into an already sorted list can be done in $\mathcal{O}(N)$ time using a three-phase approach (left disjoint, merge overlaps, right disjoint), avoiding the need to re-sort.
• Conflict Detection: To check for conflicts (as in Meeting Rooms), sort the intervals and check if any current start time is strictly less than the previous end time ($S_{\text{curr}} < E_{\text{prev}}$).
• Edge Case Vigilance: Always verify boundary conditions, such as empty inputs, single-interval inputs, nested intervals (e.g., [1, 10] and [2, 5]), and adjacent boundaries (e.g., [1, 3] and [3, 5]).