Merge Overlapping Intervals | Brute Force & Optimal Solutions

This chapter covers the classic Merge Overlapping Intervals problem. We will explore how to take an array of intervals, identify which ones overlap, and merge them into the minimum possible number of disjoint intervals. We will analyze both a naive Brute Force approach and a highly optimized Single-Pass Greedy algorithm, complete with precise time and space complexity analyses.

1. Understanding the Problem & Overlap Dynamics

An interval is represented as a pair of coordinates $[start, end]$, indicating a continuous segment from $start$ to $end$. You are given an array of $N$ such intervals. Your task is to merge all overlapping intervals and return a new array containing only the merged, mutually exclusive intervals.

Real-World Analogy: Booking Meeting Rooms

Imagine scheduling a series of meetings in a single room. If Meeting A runs from 1:00 PM to 3:00 PM ([1, 3]) and Meeting B runs from 2:00 PM to 6:00 PM ([2, 6]), these two meetings overlap. To find the total continuous block of time the room is occupied, you merge them into a single block from 1:00 PM to 6:00 PM ([1, 6]).

Why Can't We Just Merge Everything into One Large Interval?

If we have intervals like [1, 6] and [15, 18], we cannot merge them into [1, 18]. Doing so would include the empty space between $6$ and $15$ where no intervals exist. We only merge intervals that share at least one coordinate point (i.e., they overlap).

2. Visualizing Overlaps

Let's look at the example intervals used in the lecture: [[1, 3], [2, 6], [8, 9], [9, 11], [8, 10], [2, 4], [15, 18], [16, 17]]

We can visualize how these intervals lie on a 1D coordinate timeline:

By merging the overlapping segments, we get three distinct continuous blocks:

1. Block 1: From coordinate $1$ to $6$ (merging [1, 3], [2, 6], and [2, 4])
2. Block 2: From coordinate $8$ to $11$ (merging [8, 9], [8, 10], and [9, 11])
3. Block 3: From coordinate $15$ to $18$ (merging [15, 18] and [16, 17])

Final Merged Output: [[1, 6], [8, 11], [15, 18]]

3. The Importance of Sorting

If the input intervals are distributed randomly, checking for overlaps requires comparing every interval with every other interval, resulting in an inefficient $O(N^2)$ search.

By sorting the intervals based on their start times, we ensure that any potentially overlapping intervals are placed next to each other.

Sorting Rules for Pairs/Intervals:

1. Primary Sort: Sort in ascending order by the start coordinate ($interval[0]$).
2. Secondary Sort: If two intervals have the same start coordinate, sort them in ascending order by their end coordinate ($interval[1]$).

Sorted Array Example:

• Original: [[1, 3], [2, 6], [8, 9], [9, 11], [8, 10], [2, 4], [15, 18], [16, 17]]
• Sorted: [[1, 3], [2, 4], [2, 6], [8, 9], [8, 10], [9, 11], [15, 18], [16, 17]]

Once sorted, we can resolve overlaps in a linear scan because we only need to compare adjacent intervals.

4. The Brute Force Approach (Nested Loops)

The brute force approach sorts the array first, then uses nested loops to find and expand overlapping intervals.

Step-by-Step Algorithm:

1. Sort the intervals array.
2. Iterate through the array with a pointer $i$ from $0$ to $N-1$.
3. For the current interval intervals[i], let start = intervals[i][0] and end = intervals[i][1].
4. Check if already merged: If we have already processed this interval as part of a previous merged interval, skip it. We can determine this by checking if the current interval lies entirely within the last merged interval in our answer list.
5. Lookahead Loop: Use a second pointer $j$ starting from $i + 1$ to scan forward:
   • If intervals[j][0] <= end, it overlaps. Update the current interval's end: end = max(end, intervals[j][1]).
   • If intervals[j][0] > end, it does not overlap. Since the array is sorted, no subsequent interval will overlap either. Break the inner loop.
6. Push the merged interval [start, end] to the result list.
7. Move the outer pointer $i$ forward.

5. Brute Force Code Implementation

Here are the complete, production-grade implementations of the Brute Force approach in C++, Java, and Python.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> mergeOverlappingIntervalsBrute(vector<vector<int>>& intervals) {
    int n = intervals.size();
    if (n <= 1) return intervals;

    // Step 1: Sort the intervals
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> ans;

    for (int i = 0; i < n; i++) {
        int start = intervals[i][0];
        int end = intervals[i][1];

        // Step 2: Skip if the current interval is already merged in the last answer interval
        if (!ans.empty() && end <= ans.back()[1]) {
            continue;
        }

        // Step 3: Look ahead to merge all overlapping intervals
        for (int j = i + 1; j < n; j++) {
            if (intervals[j][0] <= end) {
                end = max(end, intervals[j][1]);
            } else {
                break; // No more overlaps possible
            }
        }
        ans.push_back({start, end});
    }

    return ans;
}

Java Implementation

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

public class MergeIntervalsBrute {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if (n <= 1) return intervals;

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

        List<int[]> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            // Step 2: Skip if already merged
            if (!ans.isEmpty() && end <= ans.get(ans.size() - 1)[1]) {
                continue;
            }

            // Step 3: Look ahead
            for (int j = i + 1; j < n; j++) {
                if (intervals[j][0] <= end) {
                    end = Math.max(end, intervals[j][1]);
                } else {
                    break;
                }
            }
            ans.add(new int[]{start, end});
        }

        return ans.toArray(new int[ans.size()][]);
    }
}

Python Implementation

def merge_overlapping_intervals_brute(intervals: list[list[int]]) -> list[list[int]]:
    n = len(intervals)
    if n <= 1:
        return intervals

    # Step 1: Sort intervals
    intervals.sort()

    ans = []

    for i in range(n):
        start = intervals[i][0]
        end = intervals[i][1]

        # Step 2: Skip if already merged
        if ans and end <= ans[-1][1]:
            continue

        # Step 3: Look ahead
        for j in range(i + 1, n):
            if intervals[j][0] <= end:
                end = max(end, intervals[j][1])
            else:
                break
        ans.append([start, end])

    return ans

6. Precise Complexity Analysis of Brute Force

At first glance, the nested loops might look like an $O(N^2)$ time complexity. However, a closer look reveals that it is much more efficient.

Time Complexity: $O(N \log N) + O(2N)$

• Sorting: Sorting $N$ intervals takes $O(N \log N)$ time.
• Traversal:
  • Although there is a nested loop (j loop inside i loop), we do not process every element $N$ times.
  • The continue statement skips intervals that are already merged.
  • Each interval is visited at most twice: once by the inner lookahead pointer j, and once by the outer pointer i.
  • Therefore, the total operations in the traversal phase are bounded by $2N$, which simplifies to $O(N)$.

Space Complexity: $O(N)$

• In the worst-case scenario (where no intervals overlap, e.g., [[1, 2], [3, 4], [5, 6]]), the output list ans will store all $N$ intervals. Thus, the space complexity is $O(N)$ to store the results.

7. The Optimal Approach (Single-Pass Greedy)

While the brute force approach is $O(N \log N)$, we can optimize the traversal phase to a clean, single-pass $O(N)$ scan without nested loops.

Instead of standing at an interval and looking forward to see who can merge with it, we can iterate through the sorted intervals and compare each one with the last merged interval in our answer list.

Optimal Algorithm:

1. Sort the intervals array.
2. Initialize an empty list ans.
3. Iterate through the sorted intervals from $0$ to $N-1$:
   • Case 1 (No Overlap / New Interval): If ans is empty, OR the start of the current interval is strictly greater than the end of the last interval in ans (intervals[i][0] > ans.back()[1]), then the current interval cannot be merged with the previous ones.
     • Action: Push the current interval intervals[i] directly into ans.
   • Case 2 (Overlap): If the start of the current interval is less than or equal to the end of the last interval in ans (intervals[i][0] <= ans.back()[1]), they overlap.
     • Action: Update the end of the last interval in ans to be the maximum of its current end and the current interval's end: ans.back()[1] = max(ans.back()[1], intervals[i][1]).

8. Step-by-Step Walkthrough of the Optimal Approach

Let's trace the sorted array: [[1, 3], [2, 4], [2, 6], [8, 9], [8, 10], [9, 11], [15, 18], [16, 17]]

9. Optimal Code Implementation

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> mergeOverlappingIntervalsOptimal(vector<vector<int>>& intervals) {
    int n = intervals.size();
    if (n <= 1) return intervals;

    // Step 1: Sort the intervals
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> ans;

    for (int i = 0; i < n; i++) {
        // Case 1: If ans is empty or current interval does not overlap with the last merged interval
        if (ans.empty() || intervals[i][0] > ans.back()[1]) {
            ans.push_back(intervals[i]);
        } 
        // Case 2: Overlap detected, update the end of the last merged interval
        else {
            ans.back()[1] = max(ans.back()[1], intervals[i][1]);
        }
    }

    return ans;
}

Java Implementation

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

public class MergeIntervalsOptimal {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if (n <= 1) return intervals;

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

        List<int[]> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            // Case 1: No overlap or first element
            if (ans.isEmpty() || intervals[i][0] > ans.get(ans.size() - 1)[1]) {
                ans.add(intervals[i]);
            } 
            // Case 2: Overlap, merge by updating the end coordinate
            else {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], intervals[i][1]);
            }
        }

        return ans.toArray(new int[ans.size()][]);
    }
}

Python Implementation

def merge_overlapping_intervals_optimal(intervals: list[list[int]]) -> list[list[int]]:
    if len(intervals) <= 1:
        return intervals

    # Step 1: Sort intervals
    intervals.sort()

    ans = []

    for interval in intervals:
        # Case 1: No overlap or first element
        if not ans or interval[0] > ans[-1][1]:
            ans.append(interval)
        # Case 2: Overlap, merge by updating the end coordinate
        else:
            ans[-1][1] = max(ans[-1][1], interval[1])

    return ans

10. Complexity Analysis of the Optimal Approach

The optimal approach simplifies the traversal logic, making it cleaner and faster in practice.

Time Complexity: $O(N \log N) + O(N)$

• Sorting: $O(N \log N)$ to sort the intervals.
• Single-Pass Scan: We iterate through the array exactly once. Each interval is processed in $O(1)$ constant time. Thus, the traversal takes $O(N)$ time.

Space Complexity: $O(N)$

• We use $O(N)$ space to store the merged intervals in the output list ans. No additional auxiliary space is used.

11. Edge Cases & Common Pitfalls

1. Forgetting to Use max on End Coordinates

When merging, you might be tempted to simply overwrite the end coordinate of the last merged interval with the current interval's end coordinate: ans.back()[1] = intervals[i][1] (Incorrect)

Consider this case: [[1, 5], [2, 4]]

• If you overwrite, you get [1, 4].
• If you use max(5, 4), you correctly get [1, 5].
• Rule: Always use max(last_end, current_end).

2. Handling Empty or Single-Interval Inputs

If the input array is empty or contains only one interval, sorting or accessing elements can cause out-of-bounds errors.

• Rule: Always add a guard clause at the beginning of your function:
  C++

  Copy

  if (intervals.size() <= 1) return intervals;
  

3. Modifying the Input Array

In some coding environments, modifying the input array is acceptable, while in others it is discouraged. The solutions above create a new list ans to store the results, which is clean and safe. If you need to optimize space further and are allowed to modify the input in-place, you can use a two-pointer approach on the input array itself to achieve $O(1)$ auxiliary space.

12. Comparison of Approaches

Summary and Key Takeaways

• Core Problem: Merge overlapping intervals to find the minimum number of disjoint intervals that cover the same coordinate points.
• Sorting is Key: Sorting intervals by their start times simplifies the 2D overlap problem into a 1D linear scan.
• Overlap Condition: Two sorted intervals $A$ and $B$ overlap if $B.\text{start} \le A.\text{end}$.
• Brute Force Traversal: Uses nested loops to look ahead and expand the current interval, skipping already merged intervals. This runs in $O(N \log N)$ time due to sorting, with a $O(2N)$ traversal.
• Optimal Traversal: Uses a single-pass greedy approach. It compares the current interval with the last merged interval in the answer list, running in $O(N \log N)$ time with a clean $O(N)$ traversal.
• The max Rule: When merging, always update the end coordinate using max(last_end, current_end) to handle cases where a smaller interval is completely nested inside a larger one.
• Space Complexity: Both approaches require $O(N)$ space to store the merged intervals in the worst-case scenario where no intervals overlap.