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.
Note that you don't need to modify intervals in-place. You can make a new array and return it.
Example 1
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2
Input: intervals: [[1, 3], [5, 7], [8, 12]], newInterval: [4, 6]
Output: [[1, 3], [4, 7], [8, 12]]
Explanation: After insertion, since [4, 6] overlaps with [5, 7], we merged them into one [4, 7].
Explanation
If the given list was not sorted, we could simply have appended the new interval to it and used the merge() function from Merge Intervals. But since the given list is sorted, we should try to come up with a solution better than O(N * logN).
When inserting a new interval in a sorted list, first, we need to find the correct index where the new interval can be placed. In other words, we need to skip all the intervals that end before the start of the new interval. So we can iterate through the given sorted list of intervals and skip all the intervals with the following condition:
intervals[i].end < newInterval.start
The diagram above clearly shows the merging approach. To handle all four merging scenarios, we need to do something like this:
c.start = min(a.start, b.start)
c.end = max(a.end, b.end)
Our overall algorithm will look like this:
- Skip all intervals that end before the start of the new interval, i.e., skip all
intervalswith the following conditions:
intervals[i].end < newInterval.start
2. Let’s call the last interval ‘b’ that does not satisfy the above condition. If ‘b’ overlaps with the new interval (a) (i.e. b.start <= a.end), we need to merge them into a new interval ‘c’:
c.start = min(a.start, b.start)
c.end = max(a.end, b.end)
3. We will repeat the above two steps to merge ‘c’ with the next overlapping interval.
Java Code
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int i = 0;
List<int[]> ans = new ArrayList<>();
while(i < intervals.length && intervals[i][1] < newInterval[0]) {
ans.add(intervals[i]);
i += 1;
}
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]);
i += 1;
}
ans.add(newInterval);
while(i < intervals.length) {
ans.add(intervals[i]);
i += 1;
}
return ans.toArray(new int[ans.size()][2]);
}
}
C++ Code
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int i = 0;
vector<vector<int>> ans;
while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
ans.push_back(intervals[i]);
i += 1;
}
while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i += 1;
}
ans.push_back(newInterval);
while(i < intervals.size()) {
ans.push_back(intervals[i]);
i += 1;
}
return ans;
}
};
Python Code
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
i = 0
ans = []
while i < len(intervals) and intervals[i][1] < newInterval[0]:
ans.append(intervals[i])
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])
i += 1
ans.append(newInterval)
while i < len(intervals):
ans.append(intervals[i])
i += 1
return ans
Javascript Code
var insert = function(intervals, newInterval) {
let i = 0;
const ans = [];
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
ans.push(intervals[i]);
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]);
i++;
}
ans.push(newInterval);
while (i < intervals.length) {
ans.push(intervals[i]);
i++;
}
return ans;
};
Go Code
func insert(intervals [][]int, newInterval []int) [][]int {
i := 0
var ans [][]int
for i < len(intervals) && intervals[i][1] < newInterval[0] {
ans = append(ans, intervals[i])
i++
}
for i < len(intervals) && intervals[i][0] <= newInterval[1] {
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i++
}
ans = append(ans, newInterval)
for i < len(intervals) {
ans = append(ans, intervals[i])
i++
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Complexity Analysis
Time Complexity: O(N), this is because we are iterating through all the intervals only once, the time complexity of the above algorithm is O(N), where ‘N’ is the total number of intervals.
Space Complexity: O(N), the space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals.