PPractick

The problem

A calendar app imports busy blocks from several sources, and they overlap: [1,3] from one calendar, [2,6] from another. To show a clean "busy" view, it must merge every group of overlapping (or touching) intervals into one block. After sorting by start, overlapping intervals become neighbours. Walk through them, extending the current block while the next interval starts before the block ends, and starting a new block otherwise.

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);

Test cases

Input	Output	Explanation
[[1,3],[2,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]
[[1,4],[4,5]]	[[1,5]]	Touching intervals merge
[[4,7],[1,4]]	[[1,7]]	Input need not be sorted
[[1,4],[2,3]]	[[1,4]]	Contained interval
[[1,2],[3,4]]	[[1,2],[3,4]]	A gap between 2 and 3
[[5,5]]	[[5,5]]

(Confirm: intervals are closed; intervals sharing an endpoint merge; the output is sorted by start.)

How interviewers phrase it

• "Given an array of intervals, merge all overlapping intervals and return the non-overlapping intervals that cover them" (LeetCode 56).

Clarifying questions to ask

1. Do touching intervals like [1,4] and [4,5] merge? (Yes.)
2. Is the input sorted? (No.)
3. Can I modify the input? (Sorting in place is fine.)

Follow-ups to expect

1. "Why sort by start?"
2. "Why take the max of the ends?"
3. "What if intervals arrive one by one?"
4. "How would you count the total covered length?"
5. "Complexity?"

Related questions

• Insert Interval Medium
• Non-overlapping Intervals Medium
• Assign Cookies Easy
• Sort an array of 0's 1's and 2's Medium
• Kadane's Algorithm Medium
• 3 Sum Medium

All 474 dsa interview questions

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