Merge Intervals

One of the most common interval-based interview questions is Merge Intervals. At first glance, it looks like a simulation problem, but the real trick is recognizing that sorting allows us to process all overlaps in a single pass.

Let's break it down.

Problem Statement

Given an array of intervals where:

intervals[i] = [starti, endi]

Merge all overlapping intervals and return the resulting non-overlapping intervals.

Example

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

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

Since [1,3] and [2,6] overlap, they can be merged into [1,6].

Brute Force Approach

Interview Explanation

My first observation would be that overlapping intervals need to be grouped together.

A straightforward approach is to sort the intervals and then, for every interval, keep checking future intervals that overlap with it. Whenever an overlap occurs, update the ending point and continue.

Once no overlap exists, store the merged interval and move forward.

Time Complexity

O(N²)

Space Complexity

O(N)

Brute Force Code

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

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

for (int i = 0; i < intervals.length; i++) {

    int start = intervals[i][0];
    int end = intervals[i][1];

    while (i + 1 < intervals.length &&
           intervals[i + 1][0] <= end) {

        end = Math.max(end, intervals[i + 1][1]);
        i++;
    }

    result.add(new int[]{start, end});
}

Key Observation

After sorting by start time:

[1,3] [2,6] [8,10] [15,18]

All overlapping intervals become adjacent.

This means we don't need to repeatedly compare with many future intervals.

We only need to compare with the most recently merged interval.

That observation reduces the problem to a single linear scan.

Optimal Approach

Algorithm

1. Sort intervals by start time.
2. Maintain a list of merged intervals.
3. If the current interval overlaps with the last merged interval:

• Extend the end time.

  1. Otherwise:

• Add a new interval.

Optimal Java Solution

class Solution {
    public int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

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

        for (int[] interval : intervals) {

            if (merged.isEmpty() ||
                merged.get(merged.size() - 1)[1] < interval[0]) {

                merged.add(interval);

            } else {

                merged.get(merged.size() - 1)[1] =
                    Math.max(
                        merged.get(merged.size() - 1)[1],
                        interval[1]
                    );
            }
        }

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

Dry Run

Input

[[1,3],[2,6],[8,10],[15,18]]

After Sorting

[[1,3],[2,6],[8,10],[15,18]]

Step 1

Add first interval:

[[1,3]]

Step 2

Current interval:

[2,6]

Check overlap:

2 <= 3

Yes, merge.

[[1,6]]

Step 3

Current interval:

[8,10]

Check overlap:

8 <= 6

No.

Add it.

[[1,6],[8,10]]

Step 4

Current interval:

[15,18]

Check overlap:

15 <= 10

No.

Add it.

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

What Interviewers Want To Hear

A good interview answer is:

Since interval overlap depends on ordering, I would first sort the intervals by start time. After sorting, all overlapping intervals become adjacent, allowing me to merge them in a single pass by comparing only with the most recently merged interval.

This demonstrates both pattern recognition and optimization thinking.

Complexity Analysis

Key Takeaway

Whenever you see:

• Merge intervals
• Meeting rooms
• Insert interval
• Non-overlapping intervals

Think:

Sort first. Then process intervals from left to right.

This pattern appears repeatedly in coding interviews and is worth mastering.

Striver SDE Sheet Challenge 🚀

Follow along for more daily solutions from the Striver SDE Sheet.

GitHub: https://github.com/codewithjaspreet
LinkedIn: https://linkedin.com/in/jaspreetsinghsodhi
Medium: https://medium.com/@jaspreet.dev