Insert Interval
Problem
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
intervals = [[1,3],[6,9]], newInt = [2,5][[1,5],[6,9]]def insert(intervals, new_int):
out = []
i, n = 0, len(intervals)
while i < n and intervals[i][1] < new_int[0]:
out.append(intervals[i]); i += 1
while i < n and intervals[i][0] <= new_int[1]:
new_int = [min(new_int[0], intervals[i][0]), max(new_int[1], intervals[i][1])]
i += 1
out.append(new_int)
while i < n:
out.append(intervals[i]); i += 1
return outfunction insert(intervals, newInt) {
const out = [];
let i = 0, n = intervals.length;
while (i < n && intervals[i][1] < newInt[0]) out.push(intervals[i++]);
while (i < n && intervals[i][0] <= newInt[1]) {
newInt = [Math.min(newInt[0], intervals[i][0]), Math.max(newInt[1], intervals[i][1])];
i++;
}
out.push(newInt);
while (i < n) out.push(intervals[i++]);
return out;
}class Solution {
public int[][] insert(int[][] intervals, int[] newInt) {
List<int[]> out = new ArrayList<>();
int i = 0, n = intervals.length;
while (i < n && intervals[i][1] < newInt[0]) out.add(intervals[i++]);
while (i < n && intervals[i][0] <= newInt[1]) {
newInt = new int[]{Math.min(newInt[0], intervals[i][0]), Math.max(newInt[1], intervals[i][1])};
i++;
}
out.add(newInt);
while (i < n) out.add(intervals[i++]);
return out.toArray(new int[0][]);
}
}vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int> newInt) {
vector<vector<int>> out;
int i = 0, n = intervals.size();
while (i < n && intervals[i][1] < newInt[0]) out.push_back(intervals[i++]);
while (i < n && intervals[i][0] <= newInt[1]) {
newInt = {min(newInt[0], intervals[i][0]), max(newInt[1], intervals[i][1])};
++i;
}
out.push_back(newInt);
while (i < n) out.push_back(intervals[i++]);
return out;
}Explanation
Because the existing intervals are already sorted and non-overlapping, we can insert the new one in a single left-to-right pass split into three clean phases: the intervals before, the ones that overlap, and the ones after.
First we copy every interval that ends before the new interval starts (intervals[i][1] < new_int[0]) — these are untouched.
Next, while an interval overlaps (intervals[i][0] <= new_int[1]), we absorb it by widening the new interval: new_int = [min(starts), max(ends)]. After the overlaps end, we push this merged interval once.
Finally we copy all remaining intervals, which all sit fully to the right.
Example: intervals = [[1,3],[6,9]], newInt = [2,5]. Nothing comes strictly before; [1,3] overlaps so the new interval grows to [1,5]; then [6,9] is copied, giving [[1,5],[6,9]].