function insertInterval(intervals, newInterval) {
const result = [];
let i = 0;
const n = intervals.length;
// 1. Add all intervals that end BEFORE the new interval starts.
// These cannot overlap.
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// 2. Merge all intervals that DO overlap with the new interval.
// Overlap condition: intervals[i].start <= newInterval.end
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++;
}
// Add the merged interval
result.push(newInterval);
// 3. Add all remaining intervals (those starting AFTER new interval ends)
while (i < n) {
result.push(intervals[i]);
i++;
}
return result;
}
// Usage:
const intervals = [
[1, 3],
[6, 8],
[13, 18]
];
const newInterval1 = [9, 11];
let updated = insertInterval(intervals, newInterval1);
const newInterval2 = [2, 5];
updated = insertInterval(updated, newInterval2);
console.log("Updated intervals:");
for (const iv of updated) {
process.stdout.write(`[${iv[0]},${iv[1]}] `);
}
/*
run:
Updated intervals:
[1,5] [6,8] [9,11] [13,18]
*/
