Introduction

Insert Interval is a classic interval greedy problem.

You are given:

  • A list of non-overlapping intervals sorted by start time
  • A new interval

Goal:

Insert the new interval into the list and merge overlapping intervals if necessary.

Example

Input

intervals = [[1,3],[6,9]]newInterval = [2,5]

Output

 [[1,5],[6,9]]

Explanation

[2,5] overlaps with [1,3].
After merging:
[1,5]

Key Observation

The intervals are already sorted.

Only intervals overlapping with the new interval need merging.

Algorithm

  1. Add all intervals ending before newInterval starts.
  2. Merge all overlapping intervals.
  3. Add merged interval to answer.
  4. Add remaining intervals.
  5. Return result.

Dry Run

Input

intervals = [[1,3],[6,9]]newInterval = [2,5]

First Interval

 [1,3] overlaps with [2,5]

Merge

start = min(1,2) = 1end = max(3,5) = 5
Merged Interval = [1,5]

Next Interval

 [6,9]No Overlap

Answer

 [[1,5],[6,9]]

Approach : Greedy

Traverse intervals from left to right.

Merge all intervals that overlap with the new interval and keep all non-overlapping intervals unchanged.

Practice

Complexity Analysis

Time Complexity: O(n)Explanation:
Each interval is processed at most once while traversing the array.

Space Complexity: O(n)
Explanation:
The result array may store all intervals in the worst case.

Why This Problem is Important

Insert Interval teaches interval manipulation and efficient merging without sorting.

Common Beginner Mistakes

  • Missing overlap conditions.
  • Forgetting to merge completely.
  • Adding merged interval at the wrong position.
  • Re-sorting unnecessarily.

Interview Tip

Always mention:

Since intervals are already sorted and non-overlapping, only overlapping intervals need to be merged.

Related Questions

  • Merge Intervals
  • Non-overlapping Intervals
  • Meeting Rooms
  • Employee Free Time
  • Interval List Intersections

Final Takeaway

Insert Interval is a classic interval greedy problem where we insert a new interval and merge only the overlapping intervals. Using a single traversal gives an efficient O(n) solution.