PPractick

The problem

A calendar app stores a user's busy blocks as sorted, non-overlapping intervals. When a new meeting is booked, it must be inserted and merged with any blocks it overlaps or touches, so the list stays sorted and disjoint. One linear pass handles it in three phases:

1. copy the intervals that end before the new one starts
2. absorb every interval that overlaps it, widening the new interval
3. append the merged interval, then copy the rest

Example: [[1,3], [6,9]] + [2,5] → [[1,5], [6,9]].

Function signature

vector<vector<int>> insert(const vector<vector<int>>& intervals, vector<int> newInterval);

Test cases

Input (intervals, new)	Output	Explanation
([[1,3],[6,9]], [2,5])	[[1,5],[6,9]]
([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])	[[1,2],[3,10],[12,16]]	Absorbs three intervals
([], [5,7])	[[5,7]]
([[1,5]], [2,3])	[[1,5]]	Fully contained
([[1,5]], [6,8])	[[1,5],[6,8]]	Disjoint, appended after
([[1,5]], [5,7])	[[1,7]]	Touching endpoints merge

(Confirm: intervals are closed [start, end], sorted by start and non-overlapping; intervals that touch at an endpoint count as overlapping.)

How interviewers phrase it

• "You are given an array of non-overlapping intervals sorted by start and a new interval. Insert it so the list stays sorted and non-overlapping, merging if necessary" (LeetCode 57).

Clarifying questions to ask

1. Is the input sorted and non-overlapping? (Yes.)
2. Do touching intervals merge, like [1,5] and [5,7]? (Yes, since they're closed.)
3. In place or a new list? (A new list is simplest.)

Follow-ups to expect

1. "What are the three phases?"
2. "Why is one pass enough?"
3. "Binary search?"
4. "What if the list weren't sorted?"
5. "Complexity?"

Related questions

• Merge Intervals 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