# LeetCode 57. Insert Interval

## The Problem

Link to original problem on LeetCode.

You are given an array of non-overlapping intervals `intervals`

where `intervals[i] = [start`

represent the start and the end of the _{i}, end_{i}]`i`

interval and ^{th}`intervals`

is sorted in ascending order by `start`

. You are also given an interval _{i}`newInterval = [start, end]`

that represents the start and end of another interval.

Insert `newInterval`

into `intervals`

such that `intervals`

is still sorted in ascending order by `start`

and _{i}`intervals`

still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return `intervals`

*after the insertion*.

## Examples

Example 1:

```
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
```

Example 2:

```
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

`0 <= intervals.length <= 10`

^{4}`intervals[i].length == 2`

`0 <= start`

_{i}<= end_{i}<= 10^{5}`intervals`

is sorted by`start`

in_{i}**ascending**order.`newInterval.length == 2`

`0 <= start <= end <= 10`

^{5}

## My Solution

There are three potential outcomes as we iterate over the array of intervals:

- The interval ends before the new interval, so we can just add it to the end of the
`result`

. - The new interval ends before the current interval, so we can append both the new/merged interval and all of the remaining intervals to our
`result`

. - The current interval overlaps with the new interval.

The only potentially tricky case is #3. In the case of overlapping intervals, we may need to merge them. We'll do this with a new `mergedInterval`

variable initialized to equal `newInterval`

. As we iterate across intervals, so long as there is overlap, we will update `mergedInterval`

to have the lesser start time of `mergedInterval`

and the current interval and to have the greater end time of `mergedInterval`

and the current interval. Once we reach a point in our iteration over `interval`

where there is no longer overlap, we handle case #2 and return `result`

.

Time and space complexity are both $O(n)$.

`function insert(`

intervals: [number, number][],

newInterval: [number, number],

): [number, number][] {

// Initialize a merged interval using the newInterval.

const mergedInterval: [number, number] = newInterval;

const result: [number, number][] = [];

for (let i = 0; i < intervals.length; i++) {

if (intervals[i][1] < mergedInterval[0]) {

// If the current interval ends before the new interval,

// we can safely add it to the result.

result.push(intervals[i]);

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

// If the new/merged interval ended before this one

// begins, we can safely return the combination of the

// result so far, mergedInterval, and the remainder of

// the intervals.

result.push(mergedInterval, ...intervals.slice(i));

return result;

} else {

// Otherwise, time to merge. Update in place the start

// and end times of the mergedInterval variable to be the

// minimum and maximum of what they currently are versus

// this interval respectively.

mergedInterval[0] = Math.min(intervals[i][0], mergedInterval[0]);

mergedInterval[1] = Math.max(intervals[i][1], mergedInterval[1]);

}

}

result.push(mergedInterval);

return result;

}