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.
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.
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.
Minimum number of rooms needed for a list of meetings.
Plan before you code
- Sort meetings by start.
- Keep a min-heap of end times of rooms in use.
- Reuse the room that frees up first if it is free by the new start.
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
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}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}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}- Sort by start time.
- Overlap with the last block: extend its end.
- No overlap: start a new block.
3.2Solution
Strict TypeScript, type-checked and tested.
Meeting Rooms II
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}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}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}Step by step
- Handle meetings in order of start time.
- Heap of end times: if the room that frees up first is free, reuse it.
- Push this meeting's end: a reused room or a new one.
- Rooms needed = heap size.
Complexity: O(n log n) time, O(n) space
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?
Do touching intervals overlap?
Is there another way to count rooms?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Merge all schedules, the gaps are the answer.
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
Insert Interval
Insert a new interval into a sorted, non-overlapping list and merge as needed.
- Copy intervals that end before the new one starts.
- Merge every interval that overlaps it.
- Copy the rest.
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}Complexity: O(n) time
Non-overlapping Intervals
Remove the fewest intervals so the rest do not overlap.
- Sort by end time.
- Keep an interval if it starts after the last kept end; otherwise remove it.
- Earliest end leaves the most room: the classic exchange argument.
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}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.