57. Insert Interval
Description
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16]
, insert and merge [4,9]
in as [1,2],[3,10],[12,16]
.
This is because the new interval [4,9]
overlaps with [3,5],[6,7],[8,10]
.
Solution
/**
* Definition for an interval.
* function Interval(start, end) {
* this.start = start;
* this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @param {Interval} newInterval
* @return {Interval[]}
*/
var insert = function(intervals, newInterval) {
"use strict";
let result = [];
let pos = -2;
for (let idx = 0; idx < intervals.length; idx++) {
let interval = intervals[idx];
// Push all intervals that are less than the start of the new interval
if (newInterval.start > interval.end) {
result.push(interval);
}
// Push all intervals that are greater than the end of the new interval
if (interval.start > newInterval.end) {
result.push(interval);
}
/* Find the inserted position */
// The start of the new interval is less than the current interval
if (newInterval.start < interval.start) {
// If the inserted position has not been found
if (pos === -2) {
pos = idx;
}
}
// The start of the new interval is within the current interval
if (newInterval.start >= interval.start && newInterval.start <= interval.end) {
newInterval.start = interval.start;
// If inserted position has not been found
if (pos === -2) {
pos = idx;
}
}
// The end of the new interval is within the current interval
if (newInterval.end >= interval.start && newInterval.end <= interval.end) {
newInterval.end = interval.end;
}
}
// The new interval is less than all the intervals
if (pos === -1) {
result.splice(0, 0, newInterval);
// The new interval is greater than all the intervals
} else if (pos === -2) {
result.splice(intervals.length, 0, newInterval);
} else {
result.splice(pos, 0, newInterval);
}
return result;
};