Insert an Interval Into Sorted Intervals
Problem
Given a list of non-overlapping intervals sorted by start and a new interval newInt, return the merged list. Walk the original list in three regions: copy intervals that end strictly before newInt starts, then absorb every interval that overlaps newInt by widening newInt in place, then append the merged interval and copy the remainder.
Input
intervals = [[1,3],[6,9]], newInt = [2,5]Output
[[1,5],[6,9]][2,5] swallows [1,3] → [1,5]; [6,9] is unaffected.
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;
}