Table of contents
Open Table of contents
Problem
Given an array of nonoverlapping intervals intervals
sorted in ascending order by start and a new interval newInterval
, insert newInterval
into intervals
such that intervals
remains sorted and nonoverlapping (merging overlapping intervals if necessary).
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
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: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints:
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti, endi <= 10^5
intervals
is sorted bystarti
in ascending order.newInterval.length == 2
0 <= start, end <= 10^5
Approaches
To solve this problem, we iterate through intervals
, comparing each interval to newInterval
and merging them if necessary.
Linear Scan Approach
 Add all intervals ending before
newInterval
starts: These intervals are not affected by the insertion.  Merge overlapping intervals with
newInterval
: If an interval overlaps withnewInterval
, update thenewInterval
to be the merged interval.  Add the merged
newInterval
: Once we reach an interval that starts afternewInterval
ends, add thenewInterval
.  Add remaining intervals: Add all the intervals that start after
newInterval
.
Solution: Linear Scan
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) > List[List[int]]:
result = []
i = 0
n = len(intervals)
# Add all intervals ending before newInterval starts
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Merge overlapping intervals with newInterval
while i < n and intervals[i][0] <= newInterval[1]:
newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
i += 1
result.append(newInterval)
# Add remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
Time and Memory Complexity
The time complexity is O(N), where N is the number of intervals, as we are iterating through the intervals once. The space complexity is O(N) for the output list.
Explanation
The algorithm starts by adding intervals that don’t overlap with newInterval
. Then, it merges overlapping intervals and adds the merged newInterval
. Finally, it adds the remaining intervals.
Visual Representation of the Linear Scan Approach
Consider the input intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
and newInterval = [4,8]
.

Initial Intervals and New Interval:
 Existing intervals:
[[1,2], [3,5], [6,7], [8,10], [12,16]]
.  New Interval to insert:
[4,8]
.
 Existing intervals:

Adding NonOverlapping Intervals:
 The interval
[1,2]
is added to the result as it ends before[4,8]
starts.  Result:
[[1,2]]
.
 The interval

Merging Overlapping Intervals:
 Interval
[3,5]
starts before[4,8]
ends and ends after[4,8]
starts, so it overlaps. Merge it with[4,8]
to form[3,8]
.  Interval
[6,7]
falls entirely within[3,8]
, so the merged interval remains[3,8]
.  Interval
[8,10]
overlaps with[3,8]
. Merge them to form[3,10]
.  After merging, the result is
[[1,2], [3,10]]
.
 Interval

Adding Remaining Intervals:
 Interval
[12,16]
does not overlap with[3,10]
, so it is added to the result.  Final result:
[[1,2], [3,10], [12,16]]
.
 Interval
Intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]]
New Interval: [4,8]
Step 1: Add nonoverlapping interval [1,2]
Step 2: Merge overlapping intervals [3,5], [6,7], [8,10] with [4,8] to form [3,10]
Step 3: Add remaining interval [12,16]
Result: [[1,2], [3,10], [12,16]]