Intervals & Line Sweep

At a glance

The instinct

Ranges on a number line are only hard while they are shuffled. The moment you sort them, every interval can only interact with the ones that are "still open" when it arrives, so you can walk left to right and keep a tiny summary: the last merged interval, the earliest finishing time, or a counter of how many ranges are active right now.

Almost every interval problem is one of three moves: merge (sort by start), pick the most (sort by end, greedy), or count concurrency (split into +1/-1 events and sweep).

Recognise it

Not this pattern if...

• The ranges are index windows over one array you build yourself (that is sliding window or prefix sums).
• Intervals arrive one at a time and must be queried online (that leans to an ordered set / TreeMap, e.g. My Calendar).
• You need range updates and range queries on values many times (segment tree / Fenwick territory).

Memory hack

Analogy - the hotel front desk. Guests (intervals) check in and check out. To know how many rooms you need, the clerk does not study each guest; she just walks through the day's timeline, adding one at every check-in and subtracting one at every check-out. The highest number on her tally is the answer. To fit the most guests in one room, she always gives the room to whoever leaves earliest.

Say it out loud in the interview:

1. "These are ranges, so I will sort them - by start if I merge, by end if I greedily keep as many as possible."
2. "Two ranges overlap when a.start < b.end && b.start < a.end - let me confirm whether touching endpoints count."
3. "One pass, carrying only the last kept interval / an end-time heap / an active counter."

How it works

After sorting by start, an interval can overlap the current merged block only if its start is not past the block's end. If it overlaps, stretch the block's end; otherwise close the block and open a new one. Trace for Merge Intervals on [[1,3],[8,10],[2,6],[15,18],[9,12]]:

For counting, convert each [s, e) into (s, +1) and (e, -1), sort by time, and break ties so that -1 comes first when touching endpoints do not overlap.

flowchart TD
  A["Ranges given"] --> B{"What is asked?"}
  B -->|"merge / insert / union"| C["Sort by start, extend last block"]
  B -->|"keep max / remove min / arrows"| D["Sort by end, greedy keep earliest finisher"]
  B -->|"rooms / max overlap"| E["+1 / -1 events or min-heap of ends"]
  B -->|"queries or skyline"| F["Sort events + heap of active items"]

Java template

import java.util.*;

class IntervalTemplates {
    // 1) MERGE: sort by start, extend or close the last block.
    static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] cur : intervals) {
            int[] last = out.isEmpty() ? null : out.get(out.size() - 1);
            if (last == null || cur[0] > last[1]) {   // use >= if touching ends must stay apart
                out.add(new int[]{cur[0], cur[1]});
            } else {
                last[1] = Math.max(last[1], cur[1]);  // overlap: stretch the block
            }
        }
        return out.toArray(new int[0][]);
    }

    // 2) GREEDY SELECT: max non-overlapping set (remove = n - kept).
    static int maxNonOverlapping(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int kept = 0;
        long lastEnd = Long.MIN_VALUE;
        for (int[] cur : intervals) {
            if (cur[0] >= lastEnd) {                  // use > if touching ends overlap
                kept++;
                lastEnd = cur[1];
            }
        }
        return kept;
    }
}

import java.util.*;

class SweepTemplate {
    // 3) SWEEP: maximum number of simultaneously active half-open ranges [s, e).
    static int maxConcurrent(int[][] intervals) {
        int n = intervals.length;
        int[][] events = new int[2 * n][];
        for (int i = 0; i < n; i++) {
            events[2 * i] = new int[]{intervals[i][0], +1};
            events[2 * i + 1] = new int[]{intervals[i][1], -1};
        }
        // same time: process -1 (leave) before +1 (arrive)
        Arrays.sort(events, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
                                                   : Integer.compare(a[1], b[1]));
        int active = 0, best = 0;
        for (int[] ev : events) {
            active += ev[1];
            best = Math.max(best, active);            // record any per-moment fact here
        }
        return best;
    }

    // Same answer with a min-heap of end times (Meeting Rooms II style).
    static int minRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> ends = new PriorityQueue<>();
        for (int[] cur : intervals) {
            if (!ends.isEmpty() && ends.peek() <= cur[0]) ends.poll(); // reuse a freed room
            ends.offer(cur[1]);
        }
        return ends.size();
    }
}

Complexity

Variations

• Merge / union - sort by start, stretch the last block. Merge Intervals, union length of segments.
• Insert into sorted list - copy everything ending before the new one, absorb all overlapping ones, copy the rest; no sort needed. Insert Interval.
• Activity selection (greedy by end) - keep the earliest finisher. Non-overlapping Intervals, Minimum Number of Arrows to Burst Balloons (touching counts as overlap there).
• Concurrency counting - events or end-time heap. Meeting Rooms II, car pooling, max platforms.
• Sweep with a heap of candidates - sort by start, push into a heap while sweeping time or queries. Maximum Number of Events That Can Be Attended, Minimum Interval to Include Each Query.
• Skyline / geometric sweep - critical x-points plus a max-structure of active heights. The Skyline Problem.
• Difference array - when coordinates are small integers, diff[s]++, diff[e]--, then prefix-sum.

Common mistakes

• Sorting by the wrong key: merging wants start, maximising kept intervals wants end. Sorting greedy problems by start fails on one long early interval.
• Not clarifying closed vs half-open ranges, so [1,2] and [2,3] are merged (or counted) incorrectly. Ask, then pick < or <= deliberately.
• Writing last[1] = cur[1] instead of Math.max(last[1], cur[1]) - a fully contained interval would shrink the block.
• Wrong tie-break in event sweeps: if ends and starts at the same time are not ordered correctly, the peak is over- or under-counted.

• Mutating the input array or returning references to it when the caller expects fresh output - copy intervals as you add them.

All practice problems

9 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.