# Insert Interval — LeetCode #57

Here’s my JavaScript solution to this popular challenge.

**Input**: A set of SORTED non-overlapping intervals (**intervals) **AND a new interval (**newInterval)**.

**Output**: A new set of SORTED intervals that includes the new interval. If the new interval overlaps any of the other intervals, the intervals need to be merged.

Input:intervals = [[1,3],[6,9]], newInterval = [2,5]Output:[[1,5],[6,9]]Input:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]Output:[[1,2],[3,10],[12,16]]Explanation:Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

**Constraints: **The set of intervals needs to be ordered, and there can be no overlapping.

First we can quickly determine if the following conditions are met:

- If
**intervals**set is empty, the function should immediately return**newInterval**— do not pass go, do not collect $100.

`if (!intervals.length){`

return [newInterval]

}

2. If **newInterval**’s end is before the **intervals’** first element’s start, then simply add the **newInterval** to the beginning of **intervals**. Likewise if **newInterval**’s beginning is before the **intervals’** last element’s end, then simply add the **newInterval** to the end of **intervals**.

if(newInterval[1] < intervals[0][0]){

intervals.unshift(newInterval)

return intervals

}if(newInterval[0] > intervals[intervals.length-1][1])

intervals.push(newInterval)

return intervals

}

Now, with the low lying fruit picked, we need to find if and where our **newInterval **overlaps with **intervals. **Essentially we will be finding the overlap (if it exists) and replacing the original interval(s) with the new merged interval. Or, if there is no overlap, we will be simply adding the new interval in its correct position.

To do this we set up variables for both the position and indexes of the new, possibly merged interval:

`idxBeg = 0; //These variables are the indexes of the interval(s) `

idxEnd = 0; // that will be replaced, or where newInterval needs

beg = 0; // to be placed. beg and end hold the actual range.

end = 0;

First we determine where the beginning of **newInterval **is positioned. We iterate from the beginning of **intervals **until we find an interval that either includes the **start **of **newInterval OR **starts after **newInterval’s** start. We remember the index of the interval and value of the lowest of the two.

Next we do the same with the the ending value, but this time we iterate backwards, starting from the end.

//FIND BEGINNING OF NEW RANGEfor (let i=0; i<intervals.length; i++) {

if(intervals[i][0] <= newInterval[0] && intervals[i][1] >= newInterval[0] ){

idxBeg = i;

beg = intervals[i][0]

break

} if(intervals[i][0] > newInterval[0]){

idxBeg = i

beg = newInterval[0];

break

}

}//FIND ENDING OF NEW RANGEfor (let i=intervals.length-1; i>=0; i--) {

if(intervals[i][0] <= newInterval[1] && intervals[i][1] >= newInterval[1] ){

idxEnd = i;

end = intervals[i][1]

break

} if(intervals[i][0] < newInterval[1]){

idxEnd = i

end = newInterval[1];

break

}

}

Once we determine the range of the merged interval (if it needs to be merged), we just need to replace the range of intervals with the new merged interval using **slice(***beginning index, number to be replaced, the new merged interval***)**:

`const numOfIntervalsToDelete = idxEnd - idxBeg + 1;`

intervals.splice(idxBeg, numOfIntervalsToDelete, [beg, end])

return intervals;

If no merging is necessary the **numOfIntervalsToDelete** will equal 0 and so none of the original **intervals** will be replaced and **newInterval **will be inserted in the correct location.

That’s it.