Merge Intervals

Merge Intervals

Many problems are about ranges on a line: meetings with start and end times, bookings, CPU jobs, IP ranges. Each range is an interval [start, end]. The merge intervals pattern says: sort the intervals, then sweep through them once, comparing each interval only with the last one you kept. Sorting turns a messy "does anything overlap anything?" question (O(n²) pairs) into a single ordered pass (O(n log n) total).

When do two intervals overlap?

For [a, b] and [c, d]:

overlap  ⇔  a <= d  &&  c <= b        (each starts before the other ends)

Equivalently, max(a, c) <= min(b, d). Whether touching endpoints count ([1,3] and [3,5]) depends on the problem. For merging closed intervals they usually do (use <=). For "can one person attend both meetings", a meeting ending at 3 and one starting at 3 don't clash (use <). Ask or check this every time. It's the most common off-by-one in interval problems.

Core problem: merge overlapping intervals

After sorting by start, an interval can only overlap the most recently merged interval. Anything earlier ended even sooner.

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[0][];
    Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[0]));   // sort by start

    List<int[]> merged = new ArrayList<>();
    int[] current = intervals[0].clone();
    merged.add(current);

    for (int i = 1; i < intervals.length; i++) {
        int[] next = intervals[i];
        if (next[0] <= current[1]) {                   // overlaps (or touches) the current block
            current[1] = Math.max(current[1], next[1]); // extend; max handles a fully contained interval
        } else {
            current = next.clone();                    // gap: start a new block
            merged.add(current);
        }
    }
    return merged.toArray(new int[0][]);
}

Walkthrough: after sorting, [1,3] is current. [2,6] starts at 2 ≤ 3, so extend to [1,6]. [8,10] starts at 8 > 6, so start a new block. [15,18] is also a new block.

• Time: O(n log n) for the sort, then O(n) for the sweep. Space: O(n) for the output (sorting may use O(log n) extra).
• Math.max is essential. For [1,10] followed by [2,3], the end must stay 10, not become 3.
• Use Comparator.comparingInt (or Integer.compare) rather than (a, b) -> a[0] - b[0]. The subtraction can overflow for large negative and positive values and sort incorrectly.

Variant: insert an interval into a sorted, non-overlapping list

No sort needed: the list is already sorted. Three phases: copy intervals entirely before the new one, absorb every interval that overlaps it, then copy the rest.

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> out = new ArrayList<>();
    int i = 0, n = intervals.length;
    int start = newInterval[0], end = newInterval[1];

    while (i < n && intervals[i][1] < start) out.add(intervals[i++]);        // ends before new one starts
    while (i < n && intervals[i][0] <= end) {                                // overlaps: absorb
        start = Math.min(start, intervals[i][0]);
        end   = Math.max(end, intervals[i][1]);
        i++;
    }
    out.add(new int[]{start, end});
    while (i < n) out.add(intervals[i++]);                                   // starts after it ends
    return out.toArray(new int[0][]);
}

O(n) time.

Variant: can one person attend all meetings?

Sort by start. If any meeting starts before the previous one ends, there's a clash:

Arrays.sort(meetings, Comparator.comparingInt(m -> m[0]));
for (int i = 1; i < meetings.length; i++)
    if (meetings[i][0] < meetings[i - 1][1]) return false;
return true;

Variant: minimum meeting rooms (maximum overlap)

The number of rooms needed equals the maximum number of meetings happening at the same moment. Two standard solutions:

Min-heap of end times. Sort by start. The heap holds the end times of meetings currently using a room, and the earliest-ending one is on top:

public int minMeetingRooms(int[][] meetings) {
    Arrays.sort(meetings, Comparator.comparingInt(m -> m[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    for (int[] m : meetings) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll();   // that room is free again: reuse it
        ends.offer(m[1]);
    }
    return ends.size();
}

Sweep line with sorted starts and ends. Walk both sorted arrays. Each start takes a room and each end frees one. Track the peak:

int[] starts = Arrays.stream(meetings).mapToInt(m -> m[0]).sorted().toArray();
int[] ends   = Arrays.stream(meetings).mapToInt(m -> m[1]).sorted().toArray();
int rooms = 0, peak = 0, e = 0;
for (int s : starts) {
    while (e < ends.length && ends[e] <= s) { rooms--; e++; }   // meetings finished by this start
    rooms++;
    peak = Math.max(peak, rooms);
}
return peak;

Both are O(n log n). The sweep-line idea generalizes to any "maximum concurrent X" question (peak concurrent users, maximum overlapping bookings).

Variant: fewest removals to make intervals non-overlapping

Here the greedy rule changes: sort by end, and always keep the interval that finishes first. It leaves the most room for the rest. This is the classic activity selection argument.

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[1]));   // sort by END
    int removed = 0;
    long lastEnd = Long.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= lastEnd) lastEnd = iv[1];   // keep it
        else removed++;                           // overlaps the one we kept: drop it
    }
    return removed;
}

Sort by start to merge; sort by end to choose the maximum number of non-overlapping intervals. Mixing these up is a classic mistake.

Related problems

• Interval intersection of two sorted lists: two pointers. The intersection is [max(starts), min(ends)] if non-empty, and you advance whichever interval ends first.
• Employee free time: merge everyone's busy intervals, then report the gaps between merged blocks.
• Minimum arrows to burst balloons: the same greedy as non-overlapping intervals (sort by end).

Follow-up questions this topic invites — and their answers

Q: Why is it enough to compare each interval with only the last merged one? A: After sorting by start, every earlier merged block ends no later than the last merged block (otherwise they would have merged), and the new interval starts at or after all their starts. So if it doesn't overlap the last block, it can't overlap any earlier one.

Q: What if the input is a stream of intervals arriving one at a time? A: Keep the merged intervals in a balanced tree (TreeMap keyed by start). For each new interval, find the neighbours with floorEntry and ceilingEntry, absorb any that overlap, and insert the result: O(log n) per insertion plus the removed intervals.

Q: Do touching intervals like [1,3] and [3,5] merge? A: It depends on the problem's definition. For closed intervals being merged, typically yes (<=). For meetings where one ends exactly when the next begins, they don't conflict (<). State your assumption and pick the comparison accordingly.

Q: Why sort by end time for the minimum-removals problem? A: Keeping the interval that ends earliest leaves the maximum remaining time for future intervals. An exchange argument shows that any optimal solution can be transformed to include it. Sorting by start and keeping the earliest start can pick a very long interval that blocks many short ones.

Q: What's the complexity if the intervals are already sorted? A: The sweep alone is O(n). Sorting is the only O(n log n) part, which is why problems that hand you sorted input, like Insert Interval, expect a linear solution.