Back to Problems

Insert Interval

Medium
Intervals

You are given an array of non-overlapping intervals sorted in ascending order by start_i. You are also given an interval newInterval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still has no overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Key insight: Process intervals in three phases:

  1. Add all intervals that end before the new interval starts
  2. Merge all intervals that overlap with the new interval
  3. Add all intervals that start after the new interval ends

Real-world analogy: Imagine inserting a new meeting into a calendar. You need to check if it conflicts with existing meetings and merge them if they overlap.

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps with [1,3], so they merge to [1,5]. [6,9] does not overlap.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: The new interval [4,8] overlaps with [3,5], [6,7], and [8,10], merging into [3,10].

Example 3

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation: Empty intervals list, just add the new interval.

Constraints

  • •0 <= intervals.length <= 10^4
  • •intervals[i].length == 2
  • •0 <= start_i <= end_i <= 10^5
  • •intervals is sorted by start_i in ascending order
  • •newInterval.length == 2
  • •0 <= newInterval_start <= newInterval_end <= 10^5
Show Hints (4)
Hint 1: Process intervals in three phases based on their relationship to the new interval.
Hint 2: Which intervals are completely before the new interval? (Their end < new interval start)
Hint 3: Which intervals overlap with the new interval? (They start before the new interval ends)
Hint 4: For overlapping intervals, keep track of the minimum start and maximum end.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?