Given an array of non-overlapping intervals intervals
where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]
represent the start and the end of the i<sup>th</sup>
event and intervals
is sorted in ascending order by start<sub>i</sub>
. He wants to add a new interval newInterval= [newStart, newEnd]
where newStart and newEnd represent the start and end of this interval.
Need to insert newInterval into intervals
such that intervals
is still sorted in ascending order by start<sub>i</sub>
and intervals
still does not have any overlapping intervals (merge overlapping intervals if necessary).
Examples:
Input: intervals = [[1,3], [4,5], [6,7], [8,10]], newInterval = [5,6] Output: [[1,3], [4,7], [8,10]] Explanation: The newInterval [5,6] overlaps with [4,5] and [6,7].
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,9] Output: [[1,2], [3,10], [12,16]] Explanation: The new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Constraints:
1 ≤ intervals.size() ≤ 105
0 ≤ start[i], end[i] ≤ 109Try more examples
This problem involves inserting a new interval into a sorted, non-overlapping set of intervals and ensuring the resulting intervals remain sorted and non-overlapping. It also requires merging overlapping intervals as necessary.
Key Steps to Solve the Problem:
- Determine Where to Insert the New Interval:
- Traverse the original list of intervals and insert the new interval in its appropriate position based on its
start
value.
- Traverse the original list of intervals and insert the new interval in its appropriate position based on its
- Merge Overlapping Intervals:
- After inserting the new interval, traverse the list of intervals and merge any overlapping intervals to ensure the intervals are non-overlapping.
- Preserve Sorting:
- Since the given list is already sorted and we insert the new interval at the correct position, the list remains sorted.
Algorithm:
If there is an overlap (i.e., starti <= newEnd
and endi >= newStart
), merge the overlapping intervals by updating newInterval
to:
Iterate over Intervals:
For each interval in the intervals
array, if it does not overlap with newInterval
, simply add it to the result.
If there is an overlap (i.e., starti <= newEnd
and endi >= newStart
), merge the overlapping intervals by updating newInterval
to:
newInterval[0] = min(newInterval[0], starti);
newInterval[1] = max(newInterval[1], endi);
Once the merging is complete, the resulting array will be sorted and non-overlapping.
Add Remaining Intervals:
If there are intervals after the position of the merged interval, append them to the result array.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result; // Resultant array of intervals
int i = 0, n = intervals.size();
// Step 1: Add all intervals that come before the new interval
while (i < n && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i]);
i++;
}
// Step 2: Merge overlapping intervals with newInterval
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval); // Add the merged interval
// Step 3: Add all intervals that come after the new interval
while (i < n) {
result.push_back(intervals[i]);
i++;
}
return result;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {6, 9}};
vector<int> newInterval = {2, 5};
vector<vector<int>> result = insertInterval(intervals, newInterval);
cout << "Resulting Intervals: ";
for (const auto& interval : result) {
cout << "[" << interval[0] << ", " << interval[1] << "] ";
}
cout << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
- Traversal through all intervals happens once: O(n), where
n
is the number of intervals. - Merging overlapping intervals is constant time per iteration as only the current interval and
newInterval
are involved.
- Traversal through all intervals happens once: O(n), where
- Space Complexity:
- Result is stored in a new vector: O(n).
- Space used for storing merged intervals (in the result).
Edge Cases:
- Empty Intervals:
intervals = []
andnewInterval = [5, 7]
→ Result:[[5, 7]]
.
- No Overlap:
intervals = [[1, 2], [3, 4]]
andnewInterval = [5, 6]
→ Result:[[1, 2], [3, 4], [5, 6]]
.
- Complete Overlap:
intervals = [[1, 5]]
andnewInterval = [2, 3]
→ Result:[[1, 5]]
.