Insert Interval (opens in a new tab) Medium
Problem:
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example
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].
Summary
To solve this problem, we can first identify the position where the new interval should be inserted based on its start time. We then merge any overlapping intervals by iterating over the intervals and comparing their end times with the start and end times of the new interval. We can add the merged intervals to a result list and return it as the output.
Solution:
In TypeScript:
function insertInterval(intervals: number[][], newInterval: number[]): number[][] {
let i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
i++;
}
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
intervals.splice(i, 1);
}
intervals.splice(i, 0, newInterval);
return intervals;
}In Python:
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
i = 0
while i < len(intervals) and intervals[i][1] < newInterval[0]:
i += 1
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
intervals.pop(i)
intervals.insert(i, newInterval)
return intervalsStep-by-step explanation
-
Initialize a variable i to 0, which will be used to iterate through the intervals.
-
Find the first interval that ends after the new interval starts (or the end of the input if there is no such interval). We can do this by iterating through the input intervals and comparing their end times to the start time of the new interval.
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
i++;
}- Iterate through the intervals that overlap with the new interval (i.e., their start time is before or equal to the new interval's end time). We can do this by comparing their start times to the end time of the new interval, and merging them with the new interval if there is an overlap. We also need to remove these intervals from the input array, because we don't need them anymore.
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
intervals.splice(i, 1);
}- Insert the merged new interval into the input array at the appropriate position (i.e., where we stopped iterating in the previous step). We can do this using the splice method of the array.
intervals.splice(i, 0, newInterval);- Return the modified input array, which now contains the merged intervals.
return intervals;Complexity Analysis
Time Complexity
The time complexity of this solution is O(n), where n is the length of the input list of intervals. We iterate over the intervals at most three times: once to add the intervals that end before the new interval starts, once to merge overlapping intervals, and once to add the remaining intervals.
Space Complexity
The space complexity of this solution is O(n), where n is the length of the input list of intervals. We store the merged intervals in a new list, which can have at most the same length as the input list.
Variations
Binary search
We can use binary search to find the positions where the new interval should be inserted. Then, we can merge the overlapping intervals and return the updated list of intervals.
The time complexity of the above solution is O(nlogn) because we sort the input intervals array first, and then we iterate over each interval and insert it into the merged array. The time complexity of sorting the array is O(nlogn), and iterating over each interval takes O(n) time. So the overall time complexity is O(nlogn).
The space complexity of the above solution is O(n), where n is the number of intervals. We create a new merged array to store the resulting intervals, which can be at most the same size as the input array. Additionally, we use constant space for the currentInterval variable, so the overall space complexity is O(n).
In TypeScript
function insert(intervals: number[][], newInterval: number[]): number[][] {
let n = intervals.length;
let left = 0;
let right = n - 1;
let insertIndex = n;
// Binary search to find the insertion position
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (intervals[mid][1] < newInterval[0]) {
left = mid + 1;
} else if (intervals[mid][0] > newInterval[1]) {
right = mid - 1;
insertIndex = mid;
} else {
newInterval[0] = Math.min(newInterval[0], intervals[mid][0]);
newInterval[1] = Math.max(newInterval[1], intervals[mid][1]);
intervals.splice(mid, 1);
n--;
}
}
intervals.splice(insertIndex, 0, newInterval);
return intervals;
}In Python
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
n = len(intervals)
left = 0
right = n - 1
insertIndex = n
# Binary search to find the insertion position
while left <= right:
mid = (left + right) // 2
if intervals[mid][1] < newInterval[0]:
left = mid + 1
elif intervals[mid][0] > newInterval[1]:
right = mid - 1
insertIndex = mid
else:
newInterval[0] = min(newInterval[0], intervals[mid][0])
newInterval[1] = max(newInterval[1], intervals[mid][1])
intervals.pop(mid)
n -= 1
intervals.insert(insertIndex, newInterval)
return intervalsTwo pointers
We can use two pointers to find the positions where the new interval should be inserted. Then, we can merge the overlapping intervals and return the updated list of intervals.
The time complexity of this solution is O(n), where n is the length of the input intervals array. In the worst case, we need to iterate over all the intervals to find the correct position to insert the new interval, which takes O(n) time.
The space complexity of this solution is O(n) since we are using an output array to store the merged intervals. However, if we use the input intervals array to store the merged intervals in-place, the space complexity will be O(1).
In TypeScript
function insert(intervals: number[][], newInterval: number[]): number[][] {
const result: number[][] = [];
let i = 0;
// add intervals that end before newInterval starts
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// merge overlapping intervals
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
result.push(newInterval);
// add remaining intervals
while (i < intervals.length) {
result.push(intervals[i]);
i++;
}
return result;
}In Python
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
result = []
i = 0
# add intervals that end before newInterval starts
while i < len(intervals) and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# merge overlapping intervals
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(intervals[i][0], newInterval[0])
newInterval[1] = max(intervals[i][1], newInterval[1])
i += 1
result.append(newInterval)
# add remaining intervals
while i < len(intervals):
result.append(intervals[i])
i += 1
return resultIn-place modification
As demonstrated in the solution above, we can modify the intervals in-place to insert the new interval. This can be done by iterating over the intervals and checking for overlap with the new interval. We can merge overlapping intervals and remove the old intervals that are no longer needed.