Problem
The input is a sorted list of disjoint intervals, and your goal is to insert a new interval and merge all necessary intervals returning a final new list. For example,
// if the interval list is
[[1,5], [10,15], [20,25]]
// and you need to insert the interval
[12,27]
// then your program should return the new list:
[[1,5], [10,27]]
Algorithm: 1. Create an array where the final intervals will be stored. 2. Push all the intervals into this array that come before the new interval you are adding. 3. Once we reach an interval in that comes after the new interval, add our new interval to the final array. 4. From this point, check each remaining element in the array and determine if the intervals need to be merged.
function insertInterval(arr, interval) {
var newSet = [];
var endSet = [];
var i = 0;
// add intervals that come before the new interval
while (i < arr.length && arr[i][1] < interval[0]) {
newSet.push(arr[i]);
i++;
}
// add our new interval to this final list
newSet.push(interval);
// check each interval that comes after the new interval to determine if we can merge
// if no merges are required then populate a list of the remaining intervals
while (i < arr.length) {
var last = newSet[newSet.length - 1];
if (arr[i][0] < last[1]) {
var newInterval = [Math.min.apply(null, [last[0], arr[i][0]]), Math.max.apply(null, [last[1], arr[i][1]])];
newSet[newSet.length - 1] = newInterval;
} else {
endSet.push(arr[i]);
}
i++;
}
return newSet.concat(endSet);
}
insertInterval([[1,5],[10,15],[20,25]], [12,27]);