Topic 78 of 78

Merge Intervals Pattern

Overview

The Merge Intervals pattern is used to solve problems involving overlapping schedules or ranges. If you have a list of meetings, how do you find the overlapping times? The trick is to sort all the intervals based on their START time. Once sorted, any overlapping intervals will be right next to each other in the array, allowing you to merge them linearly in a single O(N) pass.

Syntax

Sorting brings all potential overlaps together. The time complexity is dominated by the initial sort: O(N log N).

Merging Overlapping Intervals

java

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort strictly by the starting time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> result = new ArrayList<>();
    int[] currentInterval = intervals[0];
    result.add(currentInterval);
    
    for (int[] nextInterval : intervals) {
        int currentEnd = currentInterval[1];
        int nextStart = nextInterval[0];
        int nextEnd = nextInterval[1];
        
        if (currentEnd >= nextStart) { // Overlap!
            // Merge them by extending the end time
            currentInterval[1] = Math.max(currentEnd, nextEnd);
        } else {
            // No overlap, add the new interval to result and update current
            currentInterval = nextInterval;
            result.add(currentInterval);
        }
    }
    return result.toArray(new int[result.size()][]);
}

Common Pitfalls

Trying to merge without sorting the array first. It will completely fail.
Updating the end time incorrectly. It must be the `Math.max` of both intervals, because `[1, 10]` and `[2, 5]` merge into `[1, 10]`.

Interview Tips

Step 1 is ALWAYS to sort the intervals by their start time.

Real-World Example

Calendar applications (like Google Calendar) use this pattern to visually merge overlapping meeting blocks, or to find 'free time' available in your schedule.

example

java

// Merging busy calendar blocks to calculate free time.

Take Java Quiz

Topic 78 of 78

Merge Intervals Pattern

Overview

Syntax

Sorting brings all potential overlaps together. The time complexity is dominated by the initial sort: O(N log N).

Merging Overlapping Intervals

java

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort strictly by the starting time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> result = new ArrayList<>();
    int[] currentInterval = intervals[0];
    result.add(currentInterval);
    
    for (int[] nextInterval : intervals) {
        int currentEnd = currentInterval[1];
        int nextStart = nextInterval[0];
        int nextEnd = nextInterval[1];
        
        if (currentEnd >= nextStart) { // Overlap!
            // Merge them by extending the end time
            currentInterval[1] = Math.max(currentEnd, nextEnd);
        } else {
            // No overlap, add the new interval to result and update current
            currentInterval = nextInterval;
            result.add(currentInterval);
        }
    }
    return result.toArray(new int[result.size()][]);
}

Common Pitfalls

Trying to merge without sorting the array first. It will completely fail.
Updating the end time incorrectly. It must be the `Math.max` of both intervals, because `[1, 10]` and `[2, 5]` merge into `[1, 10]`.

Interview Tips

Step 1 is ALWAYS to sort the intervals by their start time.

Real-World Example

Calendar applications (like Google Calendar) use this pattern to visually merge overlapping meeting blocks, or to find 'free time' available in your schedule.

example

java

// Merging busy calendar blocks to calculate free time.

Take Java Quiz