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 you need to insert into intervals such that the intervals in the resulting array remain non-overlapping and sorted.
Return the new list of intervals after the insertion.
Inserting at that position such that:
- Interval remain sorted.
- If overlapped merge it.
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 to [1,5].
How we find the overlap?
(2)---------------(5)
(1)-----------(3)
In order to find overlaping,
For the starting point of the new interval we take the minimum from both's
starting point.
new[0] = min(1, 2)
= 1
For the end point of the new interval, we take the maximum from both's
end point.
new[1] = max(5, 3)
= 5
So the new interval is (1, 5)Example 2:
Input; inteval = [], newInterval = [5, 7]
Output: [[5, 7]]
Explanation: As there are no intervals, just insert the new interval.Different Approaches
1️⃣ Brute Force Approach
Intuition:
- As stated in the problem that intervals are already sorted in ascending order, so we can use a simple linear scan to find the appropriate place to insert the new interval.
- We handle intervals in three groups:
- Non overlapping: Intervals that come before the new interval and don't overlap.
- Overlapping intervals: Intervals that overlap with the new interval and need to be merged.
- Non overlapping intervals: Intervals that come after the new interval and don't overlap (Remaining intervals after the merging of the new interval).
Approach:
- Initialize an empty result array
result. - Iterate through the
intervals:- Before overlap: If the current interval's end is less than the new interval's start, add the current interval to
result. - Merge: If the current interval overlaps with the new interval, merge them by adjusting the start and end of the new interval.
- After overlap: If the current interval's start is greater than the new interval's end, add the new interval to the result and append all the remaining intervals.
- Before overlap: If the current interval's end is less than the new interval's start, add the current interval to
- Return the result.
Dry Run:
intervals = [
[1, 2],
[3, 5],
[6, 7],
[8, 10],
[12, 16]
]
newInterval = [4, 8]As stated in the problem that intervals are already sorted in ascending order.
First Phase (no overlap):
intervals = [
[1, 2],
[3, 5],
[6, 7],
[8, 10],
[12, 16]
]
newInterval = [4, 8]
1----2
3---------5
6----7
8--------10
11--------13
newInterval
4-------------------8
+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
results = +--------+
| |
+--------+
Pick the first interval [1, 2], as it comes before the newInterval
[4, 8]
so we add it directly to the result.Second Iteration (merge overlaps):
intervals = [
[1, 2],
[3, 5],
[6, 7],
[8, 10],
[12, 16]
]
newInterval = [4, 8]
1----2
3---------5
6----7
8--------10
11--------13
newInterval
4-------------------8
+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
results = +--------+
| [1, 2] |
+--------+
Interval [3, 5], it overlaps with the newInterval
[4, 8] since (3 <= 4),
Merge it by updating its end time as:
max(5, 8) = 8
Thus it becomes [3, 8]
Interval [6, 7] also overlaps with [3, 8], so we
further merge them into [3, 8] by doing same:
Merge it by updating its end time as:
max(7, 8) = 8
Thus it becomes [3, 8] same.
Interval [8, 10] also overlaps with [3, 8], so we
merge it:
Merge it by updating its end time as:
max(10, 8) = 10
Thus it becomes [3, 10].
Interval [12, 16] is not overlapping so, stop here
and push [3, 10] into the result.Third Phase (no overlap - remaining elements):
intervals = [
[1, 2],
[3, 5],
[6, 7],
[8, 10],
[12, 16]
]
newInterval = [4, 8]
1----2
3---------5
6----7
8--------10
11--------13
newInterval
4-------------------8
+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
results = +--------+
| [1, 2] |
+--------+
| [3, 10]|
+--------+
Interval [12, 16] comes after the newInterval [3, 10],
so add it to the result.Final Result:
results = +--------+
| [1, 2] |
+--------+
| [3, 10]|
+--------+
|[12, 16]|
+--------+Code:
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size(), i = 0;
vector<vector<int>> res;
// Step 1: Add all intervals that come before the new interval (non-overlapping)
//case 1: no overlapping case before the merge intervals
//compare ending point of intervals to starting point of newInterval
while(i < n && intervals[i][1] < newInterval[0]){
res.push_back(intervals[i]);
i++;
}
// Step 2: Merge overlapping intervals with new interval
//case 2: overlapping case and merging of intervals
while(i < n && newInterval[1] >= intervals[i][0]){
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
res.push_back(newInterval); // Add the merged interval.
// Step 3: Add all remaining intervals after the new interval.
// case 3: no overlapping of intervals after newinterval being merged
while(i < n){
res.push_back(intervals[i]);
i++;
}
return res;
}
};Complexity Analysis:
- Time Complexity:
O(n): We iterate over all intervals once, performing constant-time operations inside the loop.
- Space Complexity:
O(n): We use an output list to store the result, which can have up ton+1intervals in the worst case.- We can ignore this as it is mentioned in the problem statement to return new list.