Insert Interval

Insert Interval

1. What is this problem about?

The Insert Interval interview question is an interval merging task. You are given a list of non-overlapping intervals sorted by start time. You need to insert a newInterval into the list, merging it with any existing intervals that overlap with it, and ensuring the final list remains sorted and non-overlapping.

2. Why is this asked in interviews?

This is a standard question at Apple, Amazon, and Uber. It tests your ability to handle Array interview patterns involving ranges and overlaps. Unlike "Merge Intervals," where you sort everything first, this problem expects you to leverage the existing sorted property to achieve a linear $O(N)$ solution.

3. Algorithmic pattern used

This problem uses a Three-Phase Linear Scan.

1. Left Part: Add all intervals that end before the new interval starts.
2. Merge Part: For intervals that overlap with the new interval, update the newInterval's start to min(starts) and end to max(ends).
3. Right Part: Add all remaining intervals that start after the merged new interval ends.

4. Example explanation

Intervals: [[1, 3], [6, 9]], New: [2, 5]

1. [1, 3] overlaps with [2, 5] because $3 \geq 2$.
   • Merged: [min(1, 2), max(3, 5)] = [1, 5].
2. [6, 9] starts after [1, 5] ends.
   • No more overlap. Result: [[1, 5], [6, 9]].

5. Common mistakes candidates make

• Sorting unnecessarily: Calling sort() on the whole array ($O(N \log N)$) instead of doing a linear pass ($O(N)$).
• Merge logic errors: Forgetting that one new interval can merge with many existing ones.
• Empty inputs: Not handling cases where the original list is empty.

6. Interview preparation tip

Interval problems are all about boundary comparisons. Always check curr.end < new.start (left), curr.start > new.end (right), and the everything else case (overlap). This systematic approach prevents logic bugs in Line Sweep interview patterns.