Merge Intervals Pattern in Java: Conquer Overlapping Subarrays Efficiently

Introduction to the Merge Intervals Pattern

The Merge Intervals pattern is an essential algorithmic technique for dealing with overlapping intervals, scheduling problems, or contiguous blocks of time/space. It frequently appears in top tech interviews because it tests your ability to visualize sorting and process elements linearly based on conditional overlaps.

The core idea is simple but incredibly powerful: If you sort a list of intervals by their starting points, any intervals that overlap must be adjacent to each other in the sorted list. This simple realization reduces an $O(n^2)$ pairing problem down to $O(n \log n)$ time due to the sorting step, followed by a clean $O(n)$ linear scan.

When Should You Think About Merge Intervals?

Consider the Merge Intervals pattern when:

• You are given a list of intervals, an array of pairs, or start and end times.
• The problem asks you to merge overlapping intervals, find the intersection, or determine if any intervals overlap.
• You need to find free time blocks or schedule meetings without conflicts.
• Keywords in the prompt include "overlapping", "mutually exclusive", "contiguous", or "time slots".

Core Concept of Merge Intervals

An "interval" is generally represented as a pair of numbers [start, end]. Two intervals a and b (where a comes before b in a sorted list) can interact in exactly one of three ways:

1. Mutually Exclusive (No Overlap): a.end < b.start Example: [1, 3] and [4, 6].

2. Partial Overlap: a.end >= b.start but a.end < b.end Example: [1, 4] and [3, 6]. Here, they merge into [1, 6].

3. Complete Overlap (Subsumed): a.end >= b.end Example: [1, 6] and [2, 4]. The second interval is completely inside the first. They merge into [1, 6].

By sorting the intervals based on the start value, we guarantee that a.start <= b.start. Therefore, to check for an overlap, we only need to compare a.end with b.start.

Example: Merge Overlapping Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Brute Force Approach

A naive approach would be to compare every interval against every other interval. If they overlap, merge them and restart the checking process until no more merges can occur.

Complexity:

• Time Complexity: $O(n^2)$, or worse if we repeatedly iterate after merging.
• Space Complexity: $O(n)$ to store the result.

Optimized with the Merge Intervals Pattern

We first sort the intervals by their start times. Then, we iterate through the sorted intervals, building our result list by checking if the current interval overlaps with the last interval added to our result.

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

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

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

        List<int[]> merged = new ArrayList<>();
        
        // Step 2: Initialize the first interval
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);

        // Step 3: Iterate through the remaining intervals
        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            // If overlapping, merge them by updating the end of the current interval
            if (currentEnd >= nextStart) {
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                // If not overlapping, add the new interval to the list
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }

        // Convert the List back to an array
        return merged.toArray(new int[merged.size()][]);
    }
}

Complexity:

• Time Complexity: $O(n \log n)$ due to the sorting step. The linear scan takes $O(n)$, making the total time dominated by sorting.
• Space Complexity: $O(n)$ or $O(\log n)$ depending on the sorting algorithm implementation in Java (TimSort/Dual-Pivot Quicksort), plus $O(n)$ for the resulting list.

Dry Run: Merge Overlapping Intervals

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

Result: [[1, 6], [8, 10], [15, 18]]

Reusable Template for Merge Intervals

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

public int[][] mergeIntervalsTemplate(int[][] intervals) {
    // 1. Handle edge cases
    if (intervals.length < 2) return intervals;

    // 2. Sort by the starting point
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> result = new ArrayList<>();
    
    // 3. Initialize tracking variables
    int start = intervals[0][0];
    int end = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        int nextStart = intervals[i][0];
        int nextEnd = intervals[i][1];

        // 4. Overlap condition
        if (end >= nextStart) { 
            // Merge intervals
            end = Math.max(end, nextEnd);
        } else {
            // No overlap, finalize current and start new
            result.add(new int[]{start, end});
            start = nextStart;
            end = nextEnd;
        }
    }
    
    // 5. Don't forget to add the last processed interval
    result.add(new int[]{start, end});

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

Advanced Variation: Insert Interval

Sometimes the intervals are already sorted, and you just need to insert a new interval and merge if necessary. Because the array is already sorted, you can achieve this in strict $O(n)$ time.

Problem: Insert newInterval into intervals (which are sorted by start times) such that the resulting intervals remain sorted and non-overlapping.

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

        // Step 1: Add all intervals that come completely BEFORE the new interval
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Step 2: Merge all intervals that overlap with the new interval
        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++;
        }
        result.add(newInterval); // Add the merged new interval

        // Step 3: Add the remaining intervals
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

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

How to Recognize Merge Intervals in Interviews

Look for these clues:

• Data Shape: Arrays of arrays, lists of pairs, or objects with start and end properties.
• Concepts: "Time slots", "meetings", "schedules", "segments", "ranges".
• The Request: "Find the overlap", "merge ranges", "determine minimum rooms required", "insert a new schedule".
• Optimization Path: A naive nested loop solution can almost always be optimized to $O(n \log n)$ by sorting first.

Common Mistakes

Mistake 1: Forgetting to Sort

You cannot linearly merge intervals if they are not sorted by start time. Overlapping intervals might be at opposite ends of the array, breaking the linear scan logic. Always sort first unless explicitly told the input is sorted.

Mistake 2: Updating the Wrong End Value

When merging [1, 5] and [2, 4], the merged interval is [1, 5], not [1, 4]. Always use Math.max(currentEnd, nextEnd) to extend the boundary correctly.

Mistake 3: Forgetting the Last Interval

When using a tracking variable approach (maintaining start and end variables instead of modifying the last element in the list directly), beginners often forget to add the final interval to the result list after the loop finishes.

Practice Problems for This Pattern

1. Merge Intervals (LeetCode 56)
2. Insert Interval (LeetCode 57)
3. Non-overlapping Intervals (LeetCode 435)
4. Meeting Rooms (LeetCode 252)
5. Meeting Rooms II (LeetCode 253) - Often involves sorting start and end times separately, or using a Min-Priority Queue along with the Merge Interval logic.
6. Interval List Intersections (LeetCode 986)

Interview Script You Can Reuse

"Since the problem involves contiguous ranges and finding overlaps, the most efficient approach is the Merge Intervals pattern. First, I'll sort the intervals by their starting points. This ensures that any intervals that overlap are adjacent in the array. Then, I can iterate through the array in a single pass. If the current interval's start time is less than or equal to the previous interval's end time, an overlap exists, and I'll merge them by taking the maximum end time. If they don't overlap, I'll append the previous interval to my result set and move on. The time complexity will be bounded by the sorting step at O(n log n), and space complexity will be O(n) to store the result."

Final Takeaways

• Merge Intervals is the go-to pattern for overlapping subarrays and scheduling.
• The primary step is Sorting by start time to guarantee adjacency of overlaps.
• Overlaps are identified by checking previous.end >= current.start.
• It reduces $O(n^2)$ pairing to $O(n \log n)$ total time.

Read Next

• DSA in Java Series
• Two Pointers Pattern in Java
• Sliding Window Pattern in Java
• Fast & Slow Pointers in Java