Insert Interval
Problem
You are given an array of non-overlapping intervals
intervals
whereintervals[i] = [starti, endi]
represent the start and the end of theith
interval andintervals
is sorted in ascending order bystarti
. You are also given an intervalnewInterval = [start, end]
that represents the start and end of another interval.Insert
newInterval
intointervals
such thatintervals
is still sorted in ascending order bystarti
andintervals
still does not have any overlapping intervals (merge overlapping intervals if necessary).Return
intervals
after the insertion.
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].
Pseudocode
- if intervals overlap, merge them with [Math.min, Math.max]
- push intervals with smaller max values than merge min into left array
- push intervals wither larger min values than merge max into right array
Solution
var insert = function (intervals, newInterval) {
// this is the trick, to split array to lesser or more than merge newInterval, then reconstitute result at the end
let merge = [[], []];
const result = [];
for (let i = 0; i < intervals.length; i++) {
let currInterval = intervals[i];
const [lo, hi] = intervals[i];
if (hi < newInterval[0]) {
merge[0].push(currInterval);
} else if (newInterval[1] < lo) {
merge[1].push(currInterval);
} else {
// reassign newInterval with lowest and highest value if intervals overlap
newInterval = [
Math.min(newInterval[0], lo),
Math.max(newInterval[1], hi),
];
}
}
result.push(...merge[0], newInterval, ...merge[1]);
return result;
};
Time and Space Complexity
Time
What did the code do
Total -
Space
What did the code do
Total -
Last updated