Q27: Insert Interval
You are given an array of non-overlapping intervals sorted by start time and a newInterval. Insert newInterval into the intervals such that the list remains sorted and non-overlapping.
Linear Insert and Merge Interval
function insert(intervals, newInterval) {
const result = [];
let i = 0;
const n = intervals.length;
// Add all intervals that end before newInterval starts
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Merge all overlapping intervals with newInterval
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Add remaining intervals after newInterval
while (i < n) {
result.push(intervals[i]);
i++;
}
return result;
}
console.log(insert([[1,3],[6,9]], [2,5])); // [[1,5],[6,9]]💡 Splits the process into three distinct phases: collecting left disjoint intervals, iteratively updating the min start and max end of overlapping bounds, and collecting right disjoint intervals.
Key Takeaways
- Process non-overlapping intervals before the new interval, merge all overlapping ones, then append remaining non-overlapping intervals.
- Can be solved in a single O(N) linear pass without explicit full re-sorting.
Knowledge Check
Why is explicit array sorting not required for the Insert Interval algorithm?