Merge Intervals Explained | Backend Study Lab

Quick answer

The merge intervals pattern combines overlapping ranges by sorting them by start position and scanning once. Keep one current merged interval. If the next interval overlaps it, extend the current end; otherwise, emit the current interval and start a new one.

Sorting costs O(n log n) and the scan costs O(n). The most important design decision is not the loop—it is defining endpoint semantics. Closed intervals such as [1,3] and [3,5] overlap at 3; half-open intervals such as [1,3) and [3,5) do not.

How to recognize interval problems

Look for records with a start and end:

calendar bookings and meeting conflicts;
maintenance or deployment windows;
employee availability;
IP or numeric ranges;
reserved storage offsets;
time-series coverage;
inserting a new range into sorted ranges;
finding gaps or total covered length;
allocating the minimum number of rooms or resources.

The core question is often whether ordered ranges overlap, touch, contain one another, or leave a gap. Sorting turns an arbitrary set into a sequence where only the current merged frontier matters.

Define the interval contract first

An interval needs a representation and semantics:

record Interval(int start, int end) {
    Interval {
        if (start > end) {
            throw new IllegalArgumentException("start must be <= end");
        }
    }
}

For closed intervals [start,end], both endpoints are included. [1,3] and [3,5] overlap because both contain 3.

For half-open intervals [start,end), the start is included and the end is excluded. [1,3) ends exactly where [3,5) begins, so there is no overlap. Half-open ranges compose cleanly: their duration or length is end - start, and adjacent ranges do not double-count a boundary.

Some products intentionally merge touching half-open ranges because continuous coverage is what matters. That is a business rule, not mathematical overlap. Name it explicitly.

The sorted-frontier invariant

After sorting by start, the algorithm maintains:

Every processed interval has been fully represented in the emitted result plus one current merged interval, and no future interval can overlap an emitted interval.

Why can no future interval overlap an emitted interval? Because future starts are at least as large as the next start that already failed the overlap check.

Example with closed intervals:

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

current [1,3]
next [2,6] overlaps -> current [1,6]
next [8,10] gap     -> emit [1,6], current [8,10]
next [15,18] gap    -> emit [8,10], current [15,18]
end                 -> emit [15,18]

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

Java implementation for closed intervals

This implementation copies the input list so callers do not see it reordered:

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

static List<Interval> mergeClosed(List<Interval> intervals) {
    if (intervals == null) {
        throw new IllegalArgumentException("intervals must not be null");
    }
    if (intervals.isEmpty()) {
        return List.of();
    }
    if (intervals.stream().anyMatch(java.util.Objects::isNull)) {
        throw new IllegalArgumentException("intervals must not contain null");
    }

    List<Interval> sorted = new ArrayList<>(intervals);
    sorted.sort(
        Comparator.comparingInt(Interval::start)
            .thenComparingInt(Interval::end)
    );

    List<Interval> merged = new ArrayList<>();
    int currentStart = sorted.get(0).start();
    int currentEnd = sorted.get(0).end();

    for (int i = 1; i < sorted.size(); i++) {
        Interval next = sorted.get(i);
        if (next.start() <= currentEnd) {
            currentEnd = Math.max(currentEnd, next.end());
        } else {
            merged.add(new Interval(currentStart, currentEnd));
            currentStart = next.start();
            currentEnd = next.end();
        }
    }
    merged.add(new Interval(currentStart, currentEnd));
    return List.copyOf(merged);
}

Comparator.comparingInt and thenComparingInt avoid comparator subtraction such as a.start() - b.start(), which can overflow and violate the comparator contract.

Half-open implementation

Only the overlap predicate changes:

if (next.start() < currentEnd) {
    currentEnd = Math.max(currentEnd, next.end());
} else {
    // [currentStart,currentEnd) and [next.start,next.end) are disjoint
}

If the product wants adjacent half-open coverage merged, use <= and document that the function merges touching ranges. A method name such as mergeOverlappingOrAdjacent makes the distinction visible.

Empty half-open intervals [4,4) contain no points. Decide whether to reject, preserve, or drop them. Closed [4,4] represents one point and should not be treated the same way.

Why sort by end as a tie-breaker?

Sorting by start is sufficient for correctness if the merge uses max(end). A deterministic end tie-breaker makes behavior reproducible, simplifies dry runs, and helps tests:

[1,4], [1,2], [1,8] -> [1,2], [1,4], [1,8]

Sorting longer intervals first can also work, but the comparator and explanation must agree. Determinism matters when logs, traces, and tests show intermediate order.

Containment and duplicates

If the current interval contains the next, Math.max leaves the frontier unchanged:

current [1,10], next [3,4] -> [1,10]

Duplicate intervals collapse naturally. No special branch is required. This is a useful sign that the invariant is strong enough: containment, partial overlap, and equality all use the same update.

Insert interval variant

If existing intervals are already sorted and disjoint, inserting one interval can run in O(n) without resorting:

append intervals ending before the new interval starts;
merge every interval that overlaps the new interval;
append the remaining intervals.

For closed intervals:

static List<Interval> insertClosed(
        List<Interval> sortedDisjoint,
        Interval addition) {
    List<Interval> result = new ArrayList<>();
    int i = 0;

    while (i < sortedDisjoint.size()
            && sortedDisjoint.get(i).end() < addition.start()) {
        result.add(sortedDisjoint.get(i++));
    }

    int start = addition.start();
    int end = addition.end();
    while (i < sortedDisjoint.size()
            && sortedDisjoint.get(i).start() <= end) {
        start = Math.min(start, sortedDisjoint.get(i).start());
        end = Math.max(end, sortedDisjoint.get(i).end());
        i++;
    }
    result.add(new Interval(start, end));

    while (i < sortedDisjoint.size()) {
        result.add(sortedDisjoint.get(i++));
    }
    return List.copyOf(result);
}

This relies on a precondition: input is sorted and non-overlapping under the same endpoint semantics. Validate it at an API boundary or encode it in a dedicated type.

Merging intervals answers “what is the union?” Meeting rooms asks “what is the maximum number of simultaneous intervals?”

For room count, sort starts and ends separately or use a min-heap of active end times. Do not merge first—the merge discards concurrency depth.

Meeting conflict detection for one person is simpler: sort by start and check whether any next start is before the previous end (or <= for closed semantics). The required output determines which interval pattern to use.

Finding gaps

After merging, gaps lie between consecutive results. For half-open intervals:

static List<Interval> gaps(List<Interval> merged) {
    List<Interval> gaps = new ArrayList<>();
    for (int i = 1; i < merged.size(); i++) {
        Interval previous = merged.get(i - 1);
        Interval current = merged.get(i);
        if (previous.end() < current.start()) {
            gaps.add(new Interval(previous.end(), current.start()));
        }
    }
    return List.copyOf(gaps);
}

The Interval record alone does not carry closed versus half-open semantics, so a production library may use separate types or an enum. Mixing semantics across callers is a correctness bug.

Total covered length

Merge before summing to avoid double counting. For half-open integer or time-offset ranges:

long total = 0;
for (Interval interval : mergeHalfOpen(intervals)) {
    total += (long) interval.end() - interval.start();
}

Cast before subtraction if endpoints may span the full int range. For dates and times, use Instant, Duration, or domain units rather than an ambiguous integer.

Complexity

For arbitrary input:

copying: O(n) time and space;
sorting: O(n log n) time;
scanning: O(n) time;
output: up to O(n) intervals.

Total time is O(n log n) and auxiliary space is O(n) in this defensive implementation, excluding sorting internals.

If input is already sorted, the merge scan is O(n). Do not remove sorting merely because examples happen to arrive ordered; make sorted input a documented precondition.

Testing the Java implementation

@Test
void mergesClosedOverlapsAndTouchingEndpoints() {
    assertEquals(
        List.of(new Interval(1, 6), new Interval(8, 10)),
        mergeClosed(List.of(
            new Interval(8, 10),
            new Interval(1, 3),
            new Interval(2, 6),
            new Interval(6, 6)
        ))
    );
}

@Test
void handlesContainmentDuplicatesAndNegativeEndpoints() {
    assertEquals(
        List.of(new Interval(-5, 10)),
        mergeClosed(List.of(
            new Interval(1, 10),
            new Interval(-5, 2),
            new Interval(1, 10),
            new Interval(3, 4)
        ))
    );
}

@Test
void doesNotMutateCallerOrder() {
    List<Interval> input = new ArrayList<>(
        List.of(new Interval(8, 9), new Interval(1, 2))
    );
    mergeClosed(input);
    assertEquals(new Interval(8, 9), input.get(0));
}

Add cases for empty, one interval, all disjoint, all contained, Integer.MIN_VALUE/MAX_VALUE, null policy, and the exact closed/half-open touching rule.

Common mistakes

The first mistake is coding before defining endpoint semantics.

The second is sorting with subtraction. Overflow can produce an invalid order.

The third is mutating the caller’s list without documenting ownership.

The fourth is forgetting to emit the final current interval after the loop.

The fifth is comparing only with the previous original interval instead of the full merged frontier. [1,10], [2,3], [9,12] must become [1,12].

The sixth is applying merge intervals to a concurrency-depth question such as room count.

The seventh is claiming O(n) while silently sorting arbitrary input.

Practical checklist

Define closed, open, or half-open endpoints.
Decide whether touching ranges merge.
Validate start <= end and null policy.
Copy input unless mutation is an explicit contract.
Sort by start with a deterministic, overflow-safe comparator.
Maintain one merged frontier using max(end).
Emit the final interval.
Use long for lengths that can exceed int.
Test containment, duplicates, touching, negatives, and extreme values.
Separate union, conflict, gap, and concurrency-depth problems.
Link complexity reasoning to the Algorithms learning path.
Browse related topic clusters for adjacent patterns.

Frequently asked questions

Why does sorting make one pass sufficient?

Once starts are ordered, a future interval cannot begin before the next interval already examined. If the next start is beyond the frontier, the current interval can be finalized.

Should `[1,3]` and `[3,5]` merge?

For closed intervals, yes. For half-open intervals, they are adjacent and do not overlap, though a product may intentionally merge adjacent coverage.

Can merge intervals be O(n)?

Yes when input is already sorted under a documented precondition. Arbitrary input requires sorting, so total time is O(n log n).

Is this a two-pointers algorithm?

The main solution is a sorted scan with a frontier. Insert-interval and two-list union variants may use multiple pointers, but the invariant is more important than the label.

What type should represent time intervals?

Prefer Instant and Duration or a domain-specific type with timezone and endpoint semantics. Avoid ambiguous local timestamps or raw integers at service boundaries.

Sources and further reading

Oracle, Comparator in Java SE 25.
Oracle, List.sort in Java SE 25.
Oracle, SortedSet range-view endpoint semantics.

Read Two Pointers Algorithm Explained for ordered scans, Big-O Notation Explained for the sorting bound, and Heap Patterns Explained for meeting-room and scheduling variants. Continue through the Algorithms learning path and topic clusters.