Insert Interval
Problem Statement
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.
Constraints:
- 0 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^5
- intervals is sorted by starti in ascending order
- newInterval.length == 2
- 0 <= start <= end <= 10^5
Input Format:
- An array of intervals, sorted by start time
- A new interval to insert
Output Format:
- Return the resulting array of intervals
Examples:
Example 1:
Input:
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output:
[[1,5],[6,9]]
Explanation:
The new interval [2,5] overlaps with [1,3], so they are merged into [1,5].
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], so they are merged into [3,10].
Example 3:
Input:
intervals = [], newInterval = [5,7]
Output:
[[5,7]]
Explanation:
Since there are no intervals, just insert the new interval.
Solutions
One-Pass Approach
Process intervals in three parts: intervals that come before the new interval, intervals that overlap with the new interval, and intervals that come after the new interval.
Binary Search + Merge Approach
First use binary search to find the position where the new interval should be inserted, then merge overlapping intervals.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize result = []
- Part 1: intervals[0] = [1,3], intervals[0][1] = 3 is not < newInterval[0] = 2, so we don't add it yet
- Part 2: intervals[0] = [1,3], intervals[0][0] = 1 <= newInterval[1] = 5, so we merge
- newInterval = [min(2,1), max(5,3)] = [1,5]
- i = 1
- intervals[1] = [6,9], intervals[1][0] = 6 > newInterval[1] = 5, so we don't merge
- Add merged interval: result = [[1,5]]
- Part 3: Add intervals[1] = [6,9], result = [[1,5], [6,9]]
- Return result = [[1,5], [6,9]]
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the intervals on a number line, showing how the new interval is merged with existing intervals.
Key visualization elements:
- current interval
- merged interval
- new interval
Similar Questions
Meeting Rooms II
MediumGiven an array of meeting time intervals where intervals[i] = [starti, endi], find the minimum number of conference rooms required to hold all meetings.
Merge Intervals
MediumGiven an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Implementation Notes
This problem tests your ability to work with interval-based problems. The key insight is to handle three cases correctly: intervals before, overlapping with, and after the new interval. A one-pass solution is typically more efficient than sorting-based approaches.