Insert Interval
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.
Constraints:
- 0 <= intervals.length <= 1000
- 0 <= intervals[i].length == 2
- 0 <= newInterval[0] <= 10^5
- 0 <= newInterval[1] <= 10^5
Examples:
Input: [[1,3],[6,9]], [2,5]
Output: [[1,5],[6,9]]
Explanation: The intervals [1,3] and [2,5] overlap, so they are merged into [1,5]. The interval [6,9] remains unchanged.
Solutions
Two Pointers
Time: O(n)Space: O(n)
The solution uses two pointers to iterate through the intervals. The first pointer is used to find the position where the new interval should be inserted, and the second pointer is used to merge the overlapping intervals.
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
int i = 0;
while (i < intervals.size() && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i]);
i++;
}
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++;
}
result.push_back(newInterval);
while (i < intervals.size()) {
result.push_back(intervals[i]);
i++;
}
return result;
}Follow-up:
What if the intervals are not sorted?
