PPractick

The problem

A meeting-room booking system exports each room's bookings as [start, end] time intervals, unsorted and often overlapping (people book over each other, or extend a meeting). The facilities team wants the consolidated busy periods: overlapping or touching bookings merged into single intervals. The key step is sorting by start time. After that, every interval either extends the current busy period or starts a new one, so a single scan finishes the job.

Example: [[1, 3], [2, 6], [8, 10], [15, 18]] → [[1, 6], [8, 10], [15, 18]].

Function signature

vector<vector<int>> merge(vector<vector<int>> intervals);  // merged, sorted by start

Test cases

Input intervals	Output	Explanation
[[1,3],[2,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]	[1,3] and [2,6] overlap
[[1,4],[4,5]]	[[1,5]]	Touching intervals merge
[[1,4],[2,3]]	[[1,4]]	A contained interval disappears
[[5,6],[1,2]]	[[1,2],[5,6]]	Unsorted input
[[1,10],[2,3],[4,5],[11,12]]	[[1,10],[11,12]]	One long interval absorbs several
[[1,1]]	[[1,1]]

(Confirm: intervals are closed, so [1,4] and [4,5] overlap; the output is sorted by start.)

How interviewers phrase it

• "Merge all overlapping intervals" (LeetCode 56).
• Relatives: insert an interval (LeetCode 57), meeting rooms (can one person attend all meetings? how many rooms are needed?), non-overlapping intervals (LeetCode 435).

Clarifying questions to ask

1. Do touching intervals like [1, 4] and [4, 5] count as overlapping?
2. Is the input sorted?
3. Can I modify the input?
4. Can intervals be empty or reversed (start > end)?

Follow-ups to expect

1. "Why sort by start?"
2. "How do you merge?"
3. "Why max for the end?"
4. "How would you insert one new interval into a sorted, non-overlapping list?"
5. "Complexity?"

Related questions

• Sort an array of 0's 1's and 2's Medium
• 3 Sum Medium
• 4 Sum Medium
• Merge two sorted arrays without extra space Medium
• Insert Interval Medium
• Merge Intervals Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in