Merging Overlapping Intervals with Justified Sorting

Welcome back. In the last lesson, prefix sums turned repeated range work into a subtraction between two boundaries. This lesson uses a different way to make a global problem local: sort intervals, then scan once.

Intervals appear constantly in backend work: maintenance windows, reservation slots, time-based entitlements, address ranges, batch-processing windows, and compacted event ranges. In an interview, the code is short; the differentiator is explaining why sorting by start time makes a one-pass merge correct.

By the end, you will be able to merge all overlapping closed intervals, state the overlap rule precisely, justify the sort order, and implement the solution safely in Java.

---

1. Define the interval contract before coding

Assume each input interval is a closed range:

$$[start,end]$$

For closed intervals, both endpoints are included. Therefore, intervals overlap when the next interval begins at or before the current interval ends:

$$nextStart\le currentEnd$$

For example:

• $[1,3]$ and $[2,6]$ overlap, so their merge is $[1,6]$.
• $[1,4]$ and $[4,5]$ also overlap: both include 4, so their merge is $[1,5]$.
• $[1,4]$ and $[5,7]$ do not overlap.

The target is the minimum set of non-overlapping intervals that covers exactly the union of all input intervals.

Consider:

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

The result is:

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

We must not return [1, 18]: that would incorrectly claim that the gap between 6 and 8, and the gap between 10 and 15, are covered.

A domain detail worth stating in interviews

The condition depends on interval semantics.

Interval meaning	Do [1, 3] and [3, 5] merge?	Merge condition
Closed ranges $[start,end]$	Yes	nextStart <= currentEnd
Half-open time ranges $[start,end)$	No	nextStart < currentEnd
Business-defined “adjacent windows should combine”	Usually yes	Explicitly define the rule

For the standard Merge Intervals problem, use closed intervals and merge touching endpoints.

---

2. Why sorting by start time is the key decision

Without sorting, overlaps may be far apart:

[[6, 10], [1, 4], [7, 9], [2, 5]]

If you compare only neighboring input elements, you would miss that [1, 4] overlaps [2, 5], and [6, 10] contains [7, 9].

Sorting by start time produces:

[[1, 4], [2, 5], [6, 10], [7, 9]]

Now, every interval that could join the current merged group appears before intervals that start beyond that group’s end. This lets us maintain one active, “growing” interval.

The sorting decision is not arbitrary. Sorting by start gives a useful guarantee:

When the next interval starts after the current merged end, no later interval can overlap the current merged interval, because every later interval starts even further to the right.

That is exactly when it becomes safe to finalize the current interval.

Why not sort by end time?

Sorting by end time does not support the same simple scan.

Take:

[[1, 10], [2, 3], [4, 5]]

Sorted by end time:

[[2, 3], [4, 5], [1, 10]]

A left-to-right scan might decide that [2, 3] and [4, 5] are separate before it encounters [1, 10], which overlaps both. The decision to emit [2, 3] was premature.

Sorting by start time avoids this failure: an early interval with a long end expands the active merged range before later-starting intervals are considered.

Does the tie-breaker matter?

No special tie-breaker is required for correctness. Sort by start time only.

If two intervals share a start, they necessarily overlap:

[2, 4], [2, 8]

The merge rule retains the larger endpoint, giving [2, 8]. Sorting secondarily by end can be fine, but it is not needed.

---

3. The one-pass merge algorithm

After sorting, maintain one interval:

current = [currentStart, currentEnd]

For each next interval [nextStart, nextEnd], there are only two cases.

Case 1: It overlaps the current merged interval

If:

$$nextStart\le currentEnd$$

the ranges overlap or touch. Keep the earlier start and extend only as far as needed:

$$currentEnd=\max (currentEnd,nextEnd)$$

Using max is essential. Consider:

current = [1, 10]
next    = [2, 5]

The next interval is already fully contained. Replacing currentEnd with 5 would incorrectly shrink the range. The correct merged interval remains:

[1, 10]

Case 2: It does not overlap

If:

$$nextStart>currentEnd$$

there is a real gap. The active interval is complete, so:

1. Add it to the result.
2. Start a new active interval using the next interval.

At the end of the scan, add the final active interval. This final append is a frequent source of bugs.

---

4. Trace a complete example

Use this unsorted input:

[[6, 10], [11, 15], [2, 5], [1, 4], [7, 9]]

After sorting by start:

[[1, 4], [2, 5], [6, 10], [7, 9], [11, 15]]

Now trace the scan:

Next interval	Active interval before comparison	Decision	Active interval / result afterward
[1, 4]	none	Initialize active interval	Active: [1, 4]
[2, 5]	[1, 4]	2 <= 4, merge	Active: [1, 5]
[6, 10]	[1, 5]	6 > 5, gap	Result: [[1, 5]]; Active: [6, 10]
[7, 9]	[6, 10]	7 <= 10, merge	Active remains [6, 10]
[11, 15]	[6, 10]	11 > 10, gap	Result: [[1, 5], [6, 10]]; Active: [11, 15]
end of input	[11, 15]	Append final active interval	[[1, 5], [6, 10], [11, 15]]

Notice the containment case at [7, 9]: it overlaps [6, 10], but does not expand it.

---

5. Correctness: the invariant behind the scan

For a Principal-level interview, a brief correctness argument makes your explanation more credible than merely narrating code.

After processing each sorted interval, maintain this invariant:

The result contains finalized, mutually non-overlapping merged intervals. The active interval represents the complete union of the current connected group of overlapping intervals seen so far.

Why does each decision preserve the invariant?

• If nextStart <= currentEnd, the next interval belongs to the same connected group. Updating currentEnd to the maximum of both ends preserves the union of that group.
• If nextStart > currentEnd, the active interval cannot overlap the next interval.
• Because input is sorted by start time, all future intervals begin at or after nextStart, which is also greater than currentEnd.
• Therefore, no future interval can overlap the active interval. It is safe to finalize it.

This is the full justification for sorting by start time. Sorting creates the monotonic fact that makes “emit when a gap appears” safe.

---

6. Java implementation

This version preserves the caller’s top-level input order by sorting a shallow copy. It assumes each interval contains exactly two valid endpoints and that:

$$start\le end$$

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

public final class IntervalMerger {

    private IntervalMerger() {
    }

    public static int[][] merge(int[][] intervals) {
        Objects.requireNonNull(intervals, "intervals must not be null");

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

        // Copy the outer array so sorting does not reorder the caller's input.
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(interval -> interval[0]));

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

        int currentStart = sorted[0][0];
        int currentEnd = sorted[0][1];

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

            if (nextStart <= currentEnd) {
                currentEnd = Math.max(currentEnd, nextEnd);
            } else {
                merged.add(new int[] {currentStart, currentEnd});
                currentStart = nextStart;
                currentEnd = nextEnd;
            }
        }

        // The final active interval has not yet been emitted.
        merged.add(new int[] {currentStart, currentEnd});

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

A few representative checks:

merge(new int[][] {
    {1, 3}, {2, 6}, {8, 10}, {15, 18}
});
// [[1, 6], [8, 10], [15, 18]]

merge(new int[][] {
    {1, 4}, {4, 5}
});
// [[1, 5]]

merge(new int[][] {
    {1, 10}, {2, 3}, {4, 5}
});
// [[1, 10]]

merge(new int[][] {});
// []

Complexity

For $n$ intervals:

Component	Time	Space
Sorting by start	$O(n\log n)$	Depends on the sorting implementation
One merge scan	$O(n)$	$O(1)$ beyond output
Total	$O(n\log n)$	$O(n)$ output in the worst case

If all intervals are disjoint, the output contains $n$ intervals, so output space is $O(n)$.

This implementation also makes an $O(n)$ top-level array copy to avoid reordering the caller’s input. In a coding interview, you can sort intervals in place unless the prompt requires input preservation; simply state the choice.

---

7. Common interview mistakes

Treating touching intervals as separate

For the standard closed-interval problem, this is wrong:

if (nextStart < currentEnd)

It fails for:

[1, 4], [4, 5]

Use:

if (nextStart <= currentEnd)

unless the prompt explicitly defines half-open ranges.

Assigning the new end directly

This is wrong:

currentEnd = nextEnd;

It breaks containment:

[1, 10], [2, 5]

Always use:

currentEnd = Math.max(currentEnd, nextEnd);

Forgetting the final interval

The active interval is only appended when a later gap appears. The final one has no later interval to trigger that action, so append it after the loop.

Comparing against only the original previous interval

The comparison must use the current merged end, not merely the end of the previous raw input interval. Chained overlaps demonstrate why:

[1, 3], [2, 4], [4, 7]

The third interval overlaps the merged range [1, 4], even though it may not be handled correctly if you fail to update the active endpoint.

---

8. An interview-ready explanation

A concise explanation can sound like this:

“I’ll sort intervals by start time. After sorting, all intervals that can belong to the same connected overlapping group appear consecutively. I maintain the current merged interval. If the next interval starts at or before the current end, the intervals overlap, so I extend the end using max. Otherwise there is a gap; because all later starts are at least as large as this one, no future interval can overlap the current one, so I append it and begin a new group. Sorting dominates the runtime, so the total is $O(n\log n)$, followed by an $O(n)$ scan.”

Before coding, explicitly state:

• whether intervals are closed or half-open;
• whether touching endpoints merge;
• whether mutating input through in-place sorting is acceptable;
• how empty input should be handled.

That small amount of clarification prevents the most common correctness errors.

---

Key takeaways

• Sort intervals by start time, not by end time.
• After sorting, compare each interval only with the current merged interval.
• For closed intervals, merge when:

$$nextStart\le currentEnd$$

• When merging, update the boundary with:

$$currentEnd=\max (currentEnd,nextEnd)$$

• When nextStart > currentEnd, the current interval is final because all remaining intervals start even later.
• The overall complexity is $O(n\log n)$, dominated by sorting.

Next, you will apply the same “identify a monotonic structure, then search efficiently” mindset to binary search on a monotonic answer space.