19 — Intervals

The one decision that drives everything

Every interval problem starts with:

Sort by start, or sort by end?

Get that right and the rest is a linear scan.

Sorting by start means that as you walk forward, the only interval that can overlap the current one is the most recent block — everything earlier has been absorbed or passed. One backward look suffices.

Sorting by end enables the greedy exchange argument (20): whichever interval finishes first is always at least as good as any alternative first pick.

Overlap tests

Get these exactly right; sign errors here cause most wrong answers.

// [a0, a1] and [b0, b1] overlap (inclusive endpoints)
boolean overlap = a[0] <= b[1] && b[0] <= a[1];

// If already sorted by start (so `a` comes first), it simplifies:
boolean overlap = b[0] <= a[1];         // b starts before a ends

Why the two-sided test: two intervals overlap unless one is entirely before the other. "a ends before b starts" (a[1] < b[0]) or "b ends before a starts" (b[1] < a[0]). Negate that and you get the condition above.

Touching endpoints — always clarify

What about [1,2] and [2,3]?

Ask which applies. "Does a meeting ending at 2 conflict with one starting at 2?" is a legitimate clarifying question that interviewers expect.

Merge Intervals

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

List<int[]> merged = new ArrayList<>();
for (int[] cur : intervals) {
    if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
        merged.add(cur);                                    // disjoint — start a new block
    } else {
        int[] last = merged.get(merged.size() - 1);
        last[1] = Math.max(last[1], cur[1]);                // MAX, not cur[1]
    }
}
return merged.toArray(new int[0][]);

Why Math.max(last[1], cur[1]) and not cur[1]:

Consider [1, 10] followed by [2, 3]. They overlap, so we merge. But [2,3] is entirely inside [1,10] — assigning cur[1] would shrink the block from 10 down to 3, losing coverage.

Math.max handles both cases: partial overlap extends the block; full containment leaves it alone.

Trace: [[1,3],[2,6],[8,10],[15,18]] (already sorted)

✓

Insert Interval

The input is already sorted and non-overlapping, so no sort is needed — O(n).

Three sequential phases:

List<int[]> res = new ArrayList<>();
int i = 0, n = intervals.length;

// PHASE 1: everything strictly BEFORE the new interval
while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);

// PHASE 2: absorb everything that OVERLAPS
while (i < n && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
}
res.add(newInterval);

// PHASE 3: everything strictly AFTER
while (i < n) res.add(intervals[i++]);

return res.toArray(new int[0][]);

Writing this as three sequential while loops rather than one loop with branching is what keeps it readable. Each phase has one clear job and one clear exit condition.

Say out loud: "the input is pre-sorted, so this is O(n), not O(n log n)." It shows you read the constraints rather than reflexively sorting.

Phase 2 grows newInterval to swallow everything it touches — min on the start, max on the end.

Non-Overlapping Intervals — sort by END

Remove the minimum number of intervals so none overlap.

Reframe first: minimizing removals = maximizing how many you keep. That's the classic interval-scheduling problem.

Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));     // by END

int kept = 0, lastEnd = Integer.MIN_VALUE;
for (int[] cur : intervals) {
    if (cur[0] >= lastEnd) {          // compatible with what we've kept
        kept++;
        lastEnd = cur[1];
    }
}
return intervals.length - kept;

Why earliest-end is optimal

"Among all intervals I could take next, the one ending soonest leaves the largest remaining window for everything after. And it can be swapped into any optimal solution without loss — replacing that solution's first interval with mine only frees up more room. So the greedy choice is always safe."

Why sorting by start would be wrong

One very long early interval would be taken first and block many short ones:

[0, 100]
   [1,2] [3,4] [5,6] [7,8]

Sort by START: take [0,100], block all four short ones.  Keeps 1.
Sort by END:   take [1,2],[3,4],[5,6],[7,8].             Keeps 4.  ✓

That example is worth having ready — it makes the choice obvious in one picture.

Meeting Rooms — is there any overlap?

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
for (int i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) return false;   // starts before the previous ends
}
return true;

After sorting by start, only adjacent pairs need checking. If interval i doesn't conflict with i-1, it can't conflict with anything earlier either — those all end even sooner.

< rather than <=: a meeting starting exactly when the previous ends is fine. Confirm the convention.

Meeting Rooms II — maximum concurrency

How many rooms are needed at peak? Equivalently: what's the maximum number of intervals overlapping at any moment?

Two standard solutions, both O(n log n).

A. Min-heap of end times

The heap holds the end times of rooms currently in use.

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> endTimes = new PriorityQueue<>();

for (int[] interval : intervals) {
    if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
        endTimes.poll();                      // the earliest-finishing room is now free
    }
    endTimes.offer(interval[1]);              // this meeting occupies a room
}
return endTimes.size();

Why a min-heap: you need to know whether the earliest-finishing room has freed up by the time the next meeting starts. That's a repeated "give me the minimum" query — exactly a min-heap (14).

Why only one poll per meeting: adding one meeting can free at most one room, since the heap grows by exactly one per iteration. A while loop would also be correct but isn't necessary — the size only ever needs to shrink by one.

Trace: [[0,30],[5,10],[15,20]]

Answer: 2 rooms. ✓

B. Sweep line / chronological ordering

The idea: separate the starts from the ends and walk both timelines. You stop caring which end belongs to which start — only how many events of each kind have passed.

int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
Arrays.sort(starts);
Arrays.sort(ends);

int rooms = 0, best = 0, e = 0;
for (int s = 0; s < n; s++) {
    while (e < n && ends[e] <= starts[s]) { rooms--; e++; }    // free finished meetings
    rooms++;                                                    // this one starts
    best = Math.max(best, rooms);
}
return best;

Decoupling starts from ends is the sweep-line idea. It generalizes to "maximum number of concurrent X" for any event type.

The fully general sweep

When you need the count at every point in time:

// TreeMap<time, delta>: +1 at each start, -1 at each end, then prefix-sum in time order
TreeMap<Integer, Integer> delta = new TreeMap<>();
for (int[] iv : intervals) {
    delta.merge(iv[0], 1, Integer::sum);
    delta.merge(iv[1], -1, Integer::sum);
}
int cur = 0, best = 0;
for (int d : delta.values()) { cur += d; best = Math.max(best, cur); }

TreeMap iterates in key (time) order, so the running sum is the live count at each timestamp. This is the most flexible form — reach for it when the question asks about arbitrary points in time.

Minimum Interval to Include Each Query

The hardest in the section, and a genuine composition of three techniques: sort both inputs, sweep, and use a heap with lazy deletion.

For each query point, find the smallest interval containing it.

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

Integer[] idx = new Integer[queries.length];                 // sort queries, REMEMBER original order
for (int i = 0; i < queries.length; i++) idx[i] = i;
Arrays.sort(idx, Comparator.comparingInt(i -> queries[i]));

// min-heap by interval SIZE: {size, end}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

int[] res = new int[queries.length];
int i = 0;
for (int qi : idx) {
    int q = queries[qi];

    while (i < intervals.length && intervals[i][0] <= q) {   // add intervals that have STARTED
        pq.offer(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
        i++;
    }
    while (!pq.isEmpty() && pq.peek()[1] < q) pq.poll();     // LAZY DELETE the EXPIRED ones

    res[qi] = pq.isEmpty() ? -1 : pq.peek()[0];              // write back at the ORIGINAL index
}
return res;

Three mechanics, each reusable

1. Sort the queries but remember their original indices.

Integer[] idx holds positions, sorted by their query values. That lets you process queries in increasing order (needed for the sweep) while writing results back where the caller expects them.

Boxed Integer[] is required because Arrays.sort(int[], comparator) doesn't exist (03).

2. Offline processing.

Answering queries out of order is legitimate as long as you restore the ordering at the end. Recognizing that a problem can be solved offline is often the unlock — it lets you impose a helpful order on the work.

3. Lazy deletion.

The heap is ordered by interval size, so an expired interval could be anywhere inside it. Removing an arbitrary element costs O(n). Instead, leave it and discard stale entries only when they surface at the top.

Same device as Dijkstra's if (d > dist[node]) continue; (18).

Why O((n + q) log n): queries only increase, so every interval is pushed once and popped at most once across the entire run — the aggregate argument again.

Recognition checklist

Complexity summary