4  Merge Intervals

Rank 2 · Pattern: sort, then linear scan · Target: \(O(n\log n)\) time

4.1 Problem definition

Given a collection of intervals represented by endpoint pairs, combine every set of overlapping intervals and return the resulting non-overlapping intervals.

4.2 Clarifying questions

  1. Are intervals closed, open, or half-open? Should intervals that only touch be merged?
  2. What endpoint type and validity constraints should I assume?
  3. Can the input collection be empty?
  4. May I reorder or otherwise modify the input?
  5. In what order should I return the merged intervals?
  6. Should floating-point endpoints be compared exactly or with a tolerance?

4.3 Sample answers

  1. Intervals are half-open: [start,end). Touching intervals such as [1.5,3.25) and [3.25,5.5) remain separate.
  2. Each interval contains two finite double values with start < end; NaN, infinities, and empty intervals are invalid.
  3. Yes. Return an empty collection for empty input.
  4. Yes, although this implementation sorts a copy and leaves the input list unchanged.
  5. Return the merged intervals in ascending start order.
  6. Compare the stored double values exactly; do not apply a tolerance.

4.4 Data structures and APIs

Each implementation gives an interval named start and end values, validates the endpoint contract, sorts a copy of the input, and grows a result collection as completed intervals are emitted.

An immutable Interval record supplies accessors and value equality. List.sort uses an inline comparator with Double.compare; casting the difference between starts to int would incorrectly treat many fractional starts as equal.

A frozen dataclass supplies named fields and value equality. sorted(intervals, key=lambda interval: interval.start) returns a new list and expresses the desired key directly.

A small Copy struct supplies named fields and value equality, while Interval::new returns a Result for invalid endpoints. The borrowed slice is copied into a vector and sorted with f64::total_cmp.

Only start order is required: intervals with equal starts overlap and produce the same merged interval regardless of their relative order.

4.5 Approach and invariant

Sorting by start makes all possible partners for the current merged interval arrive consecutively. Keep that interval in current:

  1. If current.overlaps(next), replace current with current.mergeWith(next).
  2. Otherwise, they are disjoint or merely touching. No later interval can overlap the current range, so emit it and make next the new current interval.
  3. Emit the final current interval after the loop.
sorted:   [1.5------6.5)  [8.0---10.25)[10.25---12.75)
             [2.75--6.5)

merged:   [1.5------6.5)  [8.0---10.25)[10.25---12.75)

Invariant: before each iteration, merged contains all completed merged ranges, and current is the merged form of the still-open consecutive ranges.

4.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class MergeIntervalsSolution {
    record Interval(double start, double end) {
        Interval {
            if (!Double.isFinite(start) || !Double.isFinite(end)) {
                throw new IllegalArgumentException("Endpoints must be finite");
            }
            if (start >= end) {
                throw new IllegalArgumentException("start must be less than end");
            }
        }

        boolean overlaps(Interval other) {
            return start < other.end && other.start < end;
        }

        Interval mergeWith(Interval other) {
            if (!overlaps(other)) {
                throw new IllegalArgumentException("Intervals do not overlap");
            }
            return new Interval(
                Math.min(start, other.start),
                Math.max(end, other.end)
            );
        }
    }

    static List<Interval> merge(List<Interval> intervals) {
        List<Interval> merged = new ArrayList<>();
        if (intervals.isEmpty()) {
            return merged;
        }

        List<Interval> sorted = new ArrayList<>(intervals);
        sorted.sort(
            (left, right) -> Double.compare(left.start(), right.start())
        );

        Interval current = sorted.get(0);

        for (int i = 1; i < sorted.size(); i++) {
            Interval next = sorted.get(i);

            if (current.overlaps(next)) {
                current = current.mergeWith(next);
            } else {
                merged.add(current);
                current = next;
            }
        }

        merged.add(current);
        return merged;
    }

    private static Interval interval(double start, double end) {
        return new Interval(start, end);
    }

    @Test public void returnsEmptyResultForEmptyInput() {
        assertEquals(Collections.emptyList(), merge(Collections.emptyList()));
    }

    @Test public void returnsSingleIntervalUnchanged() {
        assertEquals(
            Collections.singletonList(interval(2.5, 5.5)),
            merge(Collections.singletonList(interval(2.5, 5.5)))
        );
    }

    @Test public void keepsSortedDisjointIntervalsSeparate() {
        List<Interval> input = Arrays.asList(
            interval(1.0, 2.0),
            interval(4.0, 6.0)
        );
        assertEquals(input, merge(input));
    }

    @Test public void mergesAnOverlappingPair() {
        assertEquals(
            Collections.singletonList(interval(1.0, 6.0)),
            merge(Arrays.asList(interval(1.0, 4.0), interval(3.0, 6.0)))
        );
    }

    @Test public void doesNotShrinkWhenNextIntervalIsContained() {
        assertEquals(
            Collections.singletonList(interval(1.0, 10.0)),
            merge(Arrays.asList(interval(1.0, 10.0), interval(2.0, 3.0)))
        );
    }

    @Test public void keepsTouchingIntervalsSeparate() {
        List<Interval> input = Arrays.asList(
            interval(1.5, 3.25),
            interval(3.25, 5.5)
        );
        assertEquals(input, merge(input));
    }

    @Test public void sortsUnorderedDisjointIntervals() {
        List<Interval> input = Arrays.asList(
            interval(8.5, 9.75),
            interval(-2.25, -1.5),
            interval(3.125, 4.5)
        );
        List<Interval> expected = Arrays.asList(
            interval(-2.25, -1.5),
            interval(3.125, 4.5),
            interval(8.5, 9.75)
        );
        assertEquals(expected, merge(input));
    }

    @Test public void sortsDistinctFractionalStartsCorrectly() {
        List<Interval> input = Arrays.asList(
            interval(1.4, 1.5),
            interval(0.8, 0.9)
        );
        List<Interval> expected = Arrays.asList(
            interval(0.8, 0.9),
            interval(1.4, 1.5)
        );
        assertEquals(expected, merge(input));
    }

    @Test public void mergesATransitiveOverlapChain() {
        assertEquals(
            Collections.singletonList(interval(1.0, 8.0)),
            merge(Arrays.asList(
                interval(1.0, 3.0),
                interval(2.0, 5.0),
                interval(4.0, 8.0)
            ))
        );
    }

    @Test public void emitsEachCompletedMergedGroup() {
        List<Interval> input = Arrays.asList(
            interval(1.0, 3.0),
            interval(2.0, 4.0),
            interval(7.0, 9.0),
            interval(8.0, 10.0)
        );
        List<Interval> expected = Arrays.asList(
            interval(1.0, 4.0),
            interval(7.0, 10.0)
        );
        assertEquals(expected, merge(input));
    }

    @Test public void keepsCloseButSeparateIntervalsDistinct() {
        List<Interval> input = Arrays.asList(
            interval(1.1, 2.2),
            interval(2.2000001, 3.3)
        );
        assertEquals(input, merge(input));
    }

    @Test public void mergesTheWorkedExample() {
        List<Interval> input = Arrays.asList(
            interval(1.5, 3.25),
            interval(2.75, 6.5),
            interval(8.0, 10.25),
            interval(10.25, 12.75)
        );
        List<Interval> expected = Arrays.asList(
            interval(1.5, 6.5),
            interval(8.0, 10.25),
            interval(10.25, 12.75)
        );
        assertEquals(expected, merge(input));
    }

    @Test public void doesNotReorderTheInputList() {
        List<Interval> input = new ArrayList<>(Arrays.asList(
            interval(8.0, 9.0),
            interval(1.0, 2.0)
        ));
        List<Interval> original = new ArrayList<>(input);

        merge(input);

        assertEquals(original, input);
    }

    @Test public void rejectsNonIncreasingEndpoints() {
        assertInvalidInterval(1.0, 1.0);
        assertInvalidInterval(2.0, 1.0);
    }

    @Test public void rejectsNonFiniteEndpoints() {
        assertInvalidInterval(Double.NaN, 1.0);
        assertInvalidInterval(0.0, Double.NaN);
        assertInvalidInterval(Double.NEGATIVE_INFINITY, 1.0);
        assertInvalidInterval(0.0, Double.POSITIVE_INFINITY);
    }

    private static void assertInvalidInterval(double start, double end) {
        try {
            new Interval(start, end);
            fail("Expected invalid interval [" + start + "," + end + ")");
        } catch (IllegalArgumentException expected) {
            // Expected.
        }
    }

    public static void main(String[] args) {
        JUnitCore.main("MergeIntervalsSolution");
    }
}
import math
import unittest
from dataclasses import dataclass


@dataclass(frozen=True)
class Interval:
    start: float
    end: float

    def __post_init__(self):
        if not math.isfinite(self.start) or not math.isfinite(self.end):
            raise ValueError("Endpoints must be finite")
        if self.start >= self.end:
            raise ValueError("start must be less than end")


def merge(intervals):
    if not intervals:
        return []

    sorted_intervals = sorted(intervals, key=lambda interval: interval.start)
    merged = []
    current = sorted_intervals[0]

    for next_interval in sorted_intervals[1:]:
        if next_interval.start < current.end:
            current = Interval(
                min(current.start, next_interval.start),
                max(current.end, next_interval.end),
            )
        else:
            merged.append(current)
            current = next_interval

    merged.append(current)
    return merged


class MergeIntervalsTests(unittest.TestCase):
    def test_empty_input(self):
        self.assertEqual([], merge([]))

    def test_single_interval(self):
        self.assertEqual([Interval(2.5, 5.5)], merge([Interval(2.5, 5.5)]))

    def test_merges_overlapping_intervals(self):
        self.assertEqual(
            [Interval(1.0, 6.0)],
            merge([Interval(1.0, 4.0), Interval(3.0, 6.0)]),
        )

    def test_keeps_touching_intervals_separate(self):
        intervals = [Interval(1.5, 3.25), Interval(3.25, 5.5)]
        self.assertEqual(intervals, merge(intervals))

    def test_sorts_and_merges_multiple_groups(self):
        intervals = [
            Interval(8.0, 10.25),
            Interval(2.75, 6.5),
            Interval(10.25, 12.75),
            Interval(1.5, 3.25),
        ]
        self.assertEqual(
            [
                Interval(1.5, 6.5),
                Interval(8.0, 10.25),
                Interval(10.25, 12.75),
            ],
            merge(intervals),
        )

    def test_does_not_reorder_input(self):
        intervals = [Interval(8.0, 9.0), Interval(1.0, 2.0)]
        original = intervals.copy()
        merge(intervals)
        self.assertEqual(original, intervals)

    def test_rejects_invalid_intervals(self):
        for start, end in [(1.0, 1.0), (2.0, 1.0), (math.nan, 1.0)]:
            with self.subTest(start=start, end=end):
                with self.assertRaises(ValueError):
                    Interval(start, end)


if __name__ == "__main__":
    unittest.main()
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Interval {
    start: f64,
    end: f64,
}

impl Interval {
    pub fn new(start: f64, end: f64) -> Result<Self, &'static str> {
        if !start.is_finite() || !end.is_finite() {
            return Err("endpoints must be finite");
        }
        if start >= end {
            return Err("start must be less than end");
        }
        Ok(Self { start, end })
    }
}

pub fn merge(intervals: &[Interval]) -> Vec<Interval> {
    if intervals.is_empty() {
        return Vec::new();
    }

    let mut sorted = intervals.to_vec();
    sorted.sort_by(|left, right| left.start.total_cmp(&right.start));

    let mut merged = Vec::new();
    let mut current = sorted[0];

    for next in sorted.into_iter().skip(1) {
        if next.start < current.end {
            current.end = current.end.max(next.end);
        } else {
            merged.push(current);
            current = next;
        }
    }

    merged.push(current);
    merged
}

#[cfg(test)]
mod tests {
    use super::*;

    fn interval(start: f64, end: f64) -> Interval {
        Interval::new(start, end).unwrap()
    }

    #[test]
    fn empty_input() {
        assert_eq!(Vec::<Interval>::new(), merge(&[]));
    }

    #[test]
    fn merges_overlapping_intervals() {
        assert_eq!(
            vec![interval(1.0, 6.0)],
            merge(&[interval(1.0, 4.0), interval(3.0, 6.0)])
        );
    }

    #[test]
    fn keeps_touching_intervals_separate() {
        let intervals = [interval(1.5, 3.25), interval(3.25, 5.5)];
        assert_eq!(intervals, merge(&intervals).as_slice());
    }

    #[test]
    fn sorts_and_merges_multiple_groups() {
        let intervals = [
            interval(8.0, 10.25),
            interval(2.75, 6.5),
            interval(10.25, 12.75),
            interval(1.5, 3.25),
        ];
        assert_eq!(
            vec![
                interval(1.5, 6.5),
                interval(8.0, 10.25),
                interval(10.25, 12.75),
            ],
            merge(&intervals)
        );
    }

    #[test]
    fn does_not_reorder_input() {
        let intervals = [interval(8.0, 9.0), interval(1.0, 2.0)];
        let original = intervals;
        merge(&intervals);
        assert_eq!(original, intervals);
    }

    #[test]
    fn rejects_invalid_intervals() {
        assert!(Interval::new(1.0, 1.0).is_err());
        assert!(Interval::new(2.0, 1.0).is_err());
        assert!(Interval::new(f64::NAN, 1.0).is_err());
    }
}

4.7 Worked example

After sorting the endpoint pairs [[1.5,3.25],[2.75,6.5],[8.0,10.25],[10.25,12.75]]:

next comparison state
[2.75,6.5) 2.75 < 3.25 extend current to [1.5,6.5)
[8.0,10.25) 8.0 >= 6.5 emit [1.5,6.5); current becomes [8.0,10.25)
[10.25,12.75) 10.25 < 10.25 is false emit [8.0,10.25); current becomes [10.25,12.75)
end — emit [10.25,12.75)

4.8 High-value tests

Case Input Expected
empty [] []
one [2.5,5.5) unchanged
overlap {[1.5,3.25), [2.75,6.5)} {[1.5,6.5)}
touching {[1.5,3.25), [3.25,5.5)} unchanged
containment {[1.25,10.75), [2.5,3.75)} {[1.25,10.75)}
unsorted/disjoint {[8.5,9.75), [-2.25,-1.5)} {[-2.25,-1.5), [8.5,9.75)}
close but separate {[1.1,2.2), [2.2000001,3.3)} unchanged

The overlap check compares the stored double values exactly; it does not apply a tolerance. Equality means touching, not overlap. If endpoints come from calculations that may round differently, define the domain’s tolerance policy explicitly rather than silently adding an epsilon here.

4.9 Adapting it for integer endpoints

Define the same value object with int components and compare starts with Integer.compare. The scan itself is unchanged:

record IntInterval(int start, int end) {
    IntInterval {
        if (start >= end) {
            throw new IllegalArgumentException("start must be less than end");
        }
    }

    boolean overlaps(IntInterval other) {
        return start < other.end && other.start < end;
    }

    IntInterval mergeWith(IntInterval other) {
        if (!overlaps(other)) {
            throw new IllegalArgumentException("Intervals do not overlap");
        }
        return new IntInterval(
            Math.min(start, other.start),
            Math.max(end, other.end)
        );
    }
}

sorted.sort(
    (left, right) -> Integer.compare(left.start(), right.start())
);

The merge loop can otherwise operate on List<IntInterval> exactly as it does on List<Interval>. Integer.compare also avoids the overflow risk of subtracting starts in a comparator.

4.10 Complexity and correctness

Sorting costs \(O(n\log n)\); the scan is \(O(n)\). The sorted copy and list of completed intervals use \(O(n)\) auxiliary space in the worst case, and the returned list uses \(O(n)\) output space.

If the next start is at least current.end(), every later start is also at least current.end() due to sorting. Under half-open semantics, none can overlap current, so emitting it is safe. Overlapping intervals are combined by taking the least start and greatest end, so no covered point is lost.

4.11 If the interviewer pushes

  • If mutation is acceptable, sort a caller-supplied mutable list instead of making the defensive copy.
  • If intervals arrive already sorted, skip sorting for \(O(n)\) time.
  • For a streaming sorted source, emit completed intervals lazily with \(O(1)\) working state.
  • If endpoints are closed ([start,end]), touching intervals overlap; change both comparisons in overlaps from < to <=.

4.12 TDD interview script

Start by restating the decisions that affect observable behavior: intervals are half-open, touching intervals stay separate, endpoints are finite double values with start < end, empty input is valid, and results are returned in ascending start order. Do not invent behavior for null unless the interviewer asks for it.

Then write this short test list as comments:

  1. Empty input
  2. Singleton
  3. Disjoint intervals
  4. Overlap
  5. Containment
  6. Touching intervals
  7. Unordered input
  8. Transitive overlap
  9. Multiple groups

Add only one focused test at a time. For each red–green–refactor cycle:

  1. Add a test with one clear reason to fail.
  2. Run it and confirm that it fails for the intended reason, rather than because of a compilation or fixture mistake.
  3. Make the smallest general production change that makes it pass.
  4. Run the complete MergeIntervalsSolution test class.
  5. Refactor names or duplication only while every test is green.

The tests assert public behavior, not implementation details such as whether List.sort was called. A small interval(start, end) test helper keeps the examples readable. The broad worked example is retained as an acceptance test after focused tests have driven the individual decisions.

From book/src, run the fast feedback loop with:

./java/run.sh MergeIntervalsSolution
./python/run.sh merge_intervals_solution
./rust/run.sh merge_intervals_solution

In the interview, narrate the loop: “This failing test introduces the next behavior; I will make it pass without adding unrelated behavior, rerun the suite, and then clean up.” If a new boundary test already passes because the preceding implementation was properly generalized, keep it as a regression test and do not force an unnecessary production change.

4.12.1 Pseudocode

Once the contract and test list are visible, spend less than a minute writing this design sketch before implementing the Java method:

if intervals is empty:
    return empty list

sorted = copy intervals and sort by start
merged = empty list
current = sorted[0]

for each next interval after the first:
    if next.start < current.end:       // half-open overlap
        current = interval(
            min(current.start, next.start),
            max(current.end, next.end)
        )
    else:
        add current to merged
        current = next

add current to merged                  // final flush
return merged

The loop invariant is: before each iteration, merged contains all completed merged ranges, while current is the merged form of the still-open consecutive ranges processed so far. The pseudocode is a design hypothesis; the tests still drive and verify each Java change.

4.12.2 TDD sequence

The tests are independent; their order in the source documents a useful build-up for an interview rather than a required execution order.

Step Test code added Production code added or changed
1. Empty identity returnsEmptyResultForEmptyInput Introduce merge, create the result list, and return it immediately for empty input.
2. One item and final flush returnsSingleIntervalUnchanged Initialize current from the first item and add it after the scan. This exposes the otherwise easy-to-miss final flush.
3. First completed range keepsSortedDisjointIntervalsSeparate Add the scan and its disjoint branch: emit current, then replace it with next.
4. First merge mergesAnOverlappingPair Add the overlap branch and the overlaps and mergeWith interval operations; assign the merged value back to current.
5. Boundary triangulation doesNotShrinkWhenNextIntervalIsContained and keepsTouchingIntervalsSeparate Take the maximum end when merging and use strict < comparisons. Equality must take the disjoint branch. If the earlier general implementation already passes, no production change is needed.
6. Unordered input sortsUnorderedDisjointIntervals Copy the input and sort that copy by start before scanning.
7. Comparator regression sortsDistinctFractionalStartsCorrectly Use Double.compare; this test fails for the tempting (int) (left.start() - right.start()) comparator.
8. Chained state mergesATransitiveOverlapChain Verify that every merge updates current, allowing a later interval to overlap the accumulated range. Generalize any pair-only implementation if necessary.
9. Several components emitsEachCompletedMergedGroup Exercise repeated transitions between merge and emit branches and verify that the last group is emitted.
10. Exact separation keepsCloseButSeparateIntervalsDistinct Confirm that no hidden epsilon was added to the overlap decision.
11. Acceptance example mergesTheWorkedExample Combine overlap, a gap, and touching behavior. No new branch should be necessary.
12. Chosen API guarantee doesNotReorderTheInputList Keep sorting the defensive copy. This is a documented choice of this implementation, not essential to the merge-intervals algorithm when mutation is allowed.
13. Value-object contract rejectsNonIncreasingEndpoints and rejectsNonFiniteEndpoints Add the record constructor checks for invalid ranges, NaN, and infinities. These tests harden the input contract after the core algorithm is green.

This sequence uses example triangulation to grow the behavior, boundary-value tests to distinguish < from <=, and a regression test aimed at a realistic Java comparator mistake. It stays small enough to complete under interview time pressure while giving each failure a narrow diagnostic meaning.