Intervals

The intervals coding pattern for interviews. Sort by start, merge overlaps, and sweep the line to count meeting rooms, with a step-through, templates in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level13 min read

Read first: Two pointers

An interval is a pair [start, end]: a meeting from 9 to 10, a booking from day 3 to day 7, a range of numbers. Interval problems ask which ones overlap, how to join them, or how many are running at the same time. With n intervals, comparing every pair is O(n²). Almost every interval problem gets faster with the same first step: sort.

Once the intervals are sorted by start, an overlap can only happen between neighbors in the list. You walk the list once and keep a small amount of state: the block you are building, or a count of what is open. The sort costs O(n log n), and the walk costs O(n). That’s the whole pattern. The thinking is in choosing what to sort by and what to keep while you walk.

How to spot it

The input is a list of pairs called intervals, meetings, ranges, bookings or segments.
“Merge”, “overlap”, “conflict”, “free time” or “cover”.
“How many at the same time”, such as rooms, platforms, cars or CPUs. That’s a sweep line.
“Remove the fewest” or “keep the most” intervals without overlaps. That’s a greedy choice, sorted by end.
Points on a line that start and stop something, such as passengers getting on and off a bus.

If the intervals arrive one by one and you must answer after each, sorting once is not enough. Then you need a sorted structure, such as a tree map, or a heap.

Watch it run

Merge overlapping intervals. Watch the open block on the right. Each new interval is compared with that one block only. When an interval starts after the block ends, the block is final. Every interval still to come starts even later, so none of them can reach back.

intervals, as given

merged last one is open

empty

intervals.sort(key=start)
merged = []
for start, end in intervals:
if merged and start <= merged[-1].end:
merged[-1].end = max(merged[-1].end, end)
else:
merged.append([start, end]) # a gap
return merged

Merge every group of overlapping intervals. In this order, an overlap can hide anywhere in the list.

1 / 9

Notice [5, 7]. It is compared with the block [1, 6], not with [2, 6] alone. It overlaps the block, so the block grows to [1, 7]. Also notice max in the update. An interval can sit fully inside the block, like [2, 3] inside [1, 10]. Then the end must not shrink.

The template

Merge intervals, and the fewest meeting rooms with a sweep over starts and ends:

Intervals.javaexample.pyIntervals.csmain.goexample.ts

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

public class Intervals {
    static int[][] merge(int[][] intervals) {
        // Merge overlapping intervals. After sorting by start, an interval can only overlap the
        // last merged one: every earlier merged interval ends before that one starts.
        // O(n log n) for the sort, with n intervals.
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (first, second) -> Integer.compare(first[0], second[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : sorted) {
            int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
            if (last != null && interval[0] <= last[1]) { // overlaps (or touches) the last one
                last[1] = Math.max(last[1], interval[1]); // max: the new one may sit fully inside
            } else {
                merged.add(new int[] {interval[0], interval[1]});
            }
        }
        return merged.toArray(new int[0][]);
    }

    static int minMeetingRooms(int[][] intervals) {
        // Fewest rooms so that no two meetings share one: the most meetings running at the same
        // time. Sweep the starts and the ends in time order and count how many are open.
        // O(n log n).
        int count = intervals.length;
        int[] starts = new int[count], ends = new int[count];
        for (int i = 0; i < count; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0, best = 0, endIndex = 0;
        for (int start : starts) {
            // A meeting that ends at or before this start frees its room first. Which meeting ends
            // doesn't matter, only how many are running. Every meeting has start < end, so any end
            // counted here belongs to a meeting already started, and endIndex stays in range.
            while (ends[endIndex] <= start) {
                rooms--;
                endIndex++;
            }
            rooms++;
            best = Math.max(best, rooms);
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] in = {{8, 10}, {1, 3}, {15, 18}, {2, 6}, {9, 12}, {5, 7}};
        check(Arrays.deepEquals(merge(in), new int[][] {{1, 7}, {8, 12}, {15, 18}}));
        check(Arrays.deepEquals(merge(new int[][] {{1, 4}, {4, 5}}), new int[][] {{1, 5}}));
        check(Arrays.deepEquals(merge(new int[][] {{1, 10}, {2, 3}}), new int[][] {{1, 10}}));
        check(merge(new int[0][]).length == 0);
        check(minMeetingRooms(new int[][] {{0, 30}, {5, 10}, {15, 20}}) == 2);
        check(minMeetingRooms(new int[][] {{7, 10}, {2, 4}}) == 1);
        check(minMeetingRooms(new int[][] {{1, 5}, {2, 6}, {3, 7}, {5, 8}}) == 3);
        check(minMeetingRooms(new int[0][]) == 0);
        System.out.println("ok: merge and minMeetingRooms");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

The meeting rooms sweep uses two sorted lists, one of starts and one of ends. It doesn’t need to know which end belongs to which meeting. It only needs to know how many meetings have ended before the next one starts. When an end and a start are at the same time, the end goes first. The room is free at 10 for a meeting that ends at 10.

Variations

Insert an interval

The list is already sorted and has no overlaps. A new interval arrives. Walk the list in three parts. First copy every interval that ends before the new one starts. Then merge every interval that overlaps the new one, by taking the smallest start and the largest end. Then copy the rest. That’s O(n), with no sort.

Keep the most, remove the fewest

Non-overlapping Intervals asks for the fewest removals so the rest don’t overlap. Sort by end, not by start. Walk the list and keep an interval if it starts at or after the end of the last one you kept. Otherwise remove it. Keeping the interval that ends first is always safe. Any answer that keeps a different one can swap it for this one, and nothing else gets worse. That argument is explained on the greedy page. Minimum Number of Arrows is the same problem in a different story.

Sweep line with events

Turn each interval into two events: (start, +1) and (end, -1). Sort the events by time. Put -1 before +1 at the same time if touching doesn’t count as overlap. Then walk the events and keep a running sum. The highest sum is the most intervals open at once. This works for any “how many at once” question. Car Pooling is the same idea, with +passengers and -passengers.

Meeting rooms with a heap

Sort meetings by start. Keep a min-heap of end times, one per room in use. For each meeting, if the earliest end is at or before its start, that room is free, so pop it. Then push this meeting’s end. The heap’s largest size is the answer. It’s the same O(n log n), and it also tells you which room each meeting uses.

Two sorted lists

Interval List Intersections gives two sorted lists. Use two pointers. The overlap of two intervals is [max(starts), min(ends)], if that is not empty. Then move the pointer whose interval ends first. It can’t overlap anything else in the other list.

Complexity

	Time	Extra memory
Merge intervals	O(n log n)	O(n) for output
Insert into a sorted list	O(n)	O(n) for output
Most non-overlapping (by end)	O(n log n)	O(1) beyond sort
Meeting rooms, sweep or heap	O(n log n)	O(n)
Check whether any two overlap	O(n log n)	O(1) beyond sort

Say this out loud

I’ll sort by start. Then an interval can only overlap the block I’m building, because every earlier block ends before that one starts. So one pass is enough. It’s O(n log n) for the sort and O(n) for the walk.

Interview questions

Interviewer asksWhy compare only with the last merged interval and not with all of them?

The list is sorted by start. Every block before the last one ended before the last block began. The current interval starts at or after the last block’s start. So it starts after every earlier block ended, and can’t overlap any of them. Only the last block is still open.

Interviewer asksFor the most non-overlapping intervals, why sort by end and not by start?

Sorting by start would keep [1, 100] first, and it blocks everything after it. Sorting by end keeps the interval that frees the line the soonest. Any best answer can swap its first interval for the earliest-ending one and stay valid. Repeat that argument, and the greedy choice is always as good as the best answer.

Interviewer asksThe intervals arrive one at a time, and you must answer after each. What changes?

Sorting once no longer works. Keep the merged blocks in a sorted map from start to end. For a new interval, find the block just before it and the blocks after it that it overlaps, merge them and remove the old ones. Each insert is O(log n) plus the blocks it removes. Every block is removed once at most.

Practice

10 problems on LeetCode: 2 easy, 7 medium, 1 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Five of these are solved step by step on this site, as part of the Blind 75: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms and Meeting Rooms II.

Recap

Use it when the input is a list of [start, end] pairs and the question is about overlap, merging or how many run at once.
Sort by start to merge or insert. Sort by end to keep the most.
Sweep line: open and close events, a running count, and the highest count wins.
Cost: O(n log n) for the sort, then one O(n) pass.
Watch for: whether touching counts as overlap, and max when one interval sits inside another.