Given a sorted list of non-overlapping intervals and a new interval, insert the new interval and merge if necessary. The original list is sorted by start time.
For example, given intervals [[1,3],[6,9]] and new interval [2,5], the result is [[1,5],[6,9]].
Another example: intervals [[1,2],[3,5],[6,7],[8,10],[12,16]] and new interval [4,8] gives [[1,2],[3,10],[12,16]].
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
Since the list is already sorted, you can split the problem into three phases: intervals entirely before the new one, intervals that overlap, and intervals entirely after.
- Hint 2
An existing interval is entirely before the new interval if its end is less than the new interval's start.
- Hint 3
While intervals overlap with the new one, keep merging by updating the new interval's start to the minimum and its end to the maximum.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.