Intervals pattern

Sort by start, then sweep and merge.

Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

After sorting by start, an interval overlaps the last merged one only if its start ≤ that end. For 'how many at once', sweep start and end events in order.

Why it works

Once intervals are sorted by start, an interval can only overlap the last one in the merged list, so a single pass decides 'merge' or 'append'. For counting rooms, sorting by start and watching the earliest end time tells you whether a room has freed up.

Typical cost: O(n log n) time for the sort

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Meetings, bookings, rangesMerge or insert overlapping rangesMinimum rooms or arrowsFree time between schedules
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Meeting Rooms II

The problem statement, then the plan you would say out loud.

Problem

Minimum number of rooms needed for a list of meetings.

Plan before you code

  1. Sort meetings by start.
  2. Keep a min-heap of end times of rooms in use.
  3. Reuse the room that frees up first if it is free by the new start.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

Merge overlapping intervals

TypeScriptKotlinJava
merge-overlapping-intervals.tsTypeScriptCopy
1function merge(intervals: number[][]): number[][] {2  intervals.sort((a, b) => a[0] - b[0]);3  const merged: number[][] = [];4  for (const [start, end] of intervals) {5    const last = merged[merged.length - 1];6    if (last && start <= last[1]) last[1] = Math.max(last[1], end);7    else merged.push([start, end]);8  }9  return merged;10}
10 linesUTF-8TypeScript
merge-overlapping-intervals.ktKotlinCopy
1fun merge(intervals: Array<IntArray>): List<IntArray> {2    intervals.sortBy { it[0] }3    val merged = ArrayList<IntArray>()4    for ((start, end) in intervals) {5        val last = merged.lastOrNull()6        if (last != null && start <= last[1]) last[1] = maxOf(last[1], end)7        else merged.add(intArrayOf(start, end))8    }9    return merged10}
10 linesUTF-8Kotlin
merge-overlapping-intervals.javaJavaCopy
1static int[][] merge(int[][] intervals) {2  Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));3  List<int[]> merged = new ArrayList<>();4  for (int[] cur : intervals) {5    int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);6    if (last != null && cur[0] <= last[1]) last[1] = Math.max(last[1], cur[1]);7    else merged.add(new int[] {cur[0], cur[1]});8  }9  return merged.toArray(new int[0][]);10}
10 linesUTF-8Java
  1. Sort by start time.
  2. Overlap with the last block: extend its end.
  3. No overlap: start a new block.

3.2Solution

Strict TypeScript, type-checked and tested.

Meeting Rooms II

TypeScriptKotlinJava
meeting-rooms-ii.tsTypeScriptCopy
1function minRooms(meetings: number[][]): number {2  meetings.sort((a, b) => a[0] - b[0]);3  const ends = new MinHeap<number>((x, y) => x < y);4  for (const [start, end] of meetings) {5    if (ends.size && ends.peek()! <= start) ends.pop();   // reuse a room6    ends.push(end);7  }8  return ends.size;9}
9 linesUTF-8TypeScript
meeting-rooms-ii.ktKotlinCopy
1fun minRooms(meetings: Array<IntArray>): Int {2    meetings.sortBy { it[0] }3    val ends = PriorityQueue<Int>()4    for ((start, end) in meetings) {5        if (ends.isNotEmpty() && ends.peek() <= start) ends.poll()   // reuse a room6        ends.add(end)7    }8    return ends.size9}
9 linesUTF-8Kotlin
meeting-rooms-ii.javaJavaCopy
1static int minRooms(int[][] meetings) {2  Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));3  PriorityQueue<Integer> ends = new PriorityQueue<>();4  for (int[] m : meetings) {5    if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll();   // reuse a room6    ends.add(m[1]);7  }8  return ends.size();9}
9 linesUTF-8Java

Step by step

  1. Handle meetings in order of start time.
  2. Heap of end times: if the room that frees up first is free, reuse it.
  3. Push this meeting's end: a reused room or a new one.
  4. Rooms needed = heap size.

Complexity: O(n log n) time, O(n) space

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

Sort by start or by end?
By start to merge or count overlaps; by end for greedy selection, such as keeping the most non-overlapping intervals.
Do touching intervals overlap?
Ask. [1, 2] and [2, 3] may or may not clash depending on whether a meeting can start the minute another ends. State your assumption.
Is there another way to count rooms?
A sweep line: +1 at every start, −1 at every end, processed in time order with ends before starts at equal times. The highest running total is the answer.

4.2Solo practice

Try these without looking; open the hint only when stuck.

HardEmployee Free Time
Hint

Merge all schedules, the gaps are the answer.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Insert Interval

Insert a new interval into a sorted, non-overlapping list and merge as needed.

  1. Copy intervals that end before the new one starts.
  2. Merge every interval that overlaps it.
  3. Copy the rest.
insert-interval.tsTypeScriptCopy
1function insert(intervals: number[][], add: number[]): number[][] {2  const out: number[][] = [];3  const n = intervals.length;4  let i = 0;5  while (i < n && intervals[i][1] < add[0]) out.push(intervals[i++]);6  let [start, end] = add;7  while (i < n && intervals[i][0] <= end) {8    start = Math.min(start, intervals[i][0]);9    end = Math.max(end, intervals[i][1]);10    i++;11  }12  out.push([start, end], ...intervals.slice(i));13  return out;14}
14 linesUTF-8TypeScript

Complexity: O(n) time

Medium

Non-overlapping Intervals

Remove the fewest intervals so the rest do not overlap.

  1. Sort by end time.
  2. Keep an interval if it starts after the last kept end; otherwise remove it.
  3. Earliest end leaves the most room: the classic exchange argument.
nonoverlapping-intervals.tsTypeScriptCopy
1function eraseOverlapIntervals(intervals: number[][]): number {2  intervals.sort((a, b) => a[1] - b[1]);3  let removed = 0, end = -Infinity;4  for (const [s, e] of intervals) {5    if (s >= end) end = e;6    else removed++;7  }8  return removed;9}
9 linesUTF-8TypeScript

Complexity: O(n log n) time

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Sorting by end when you need start (or vice versa)
  • Touching intervals: is [1,2] and [2,3] an overlap? Ask.