In this approach, we'll first identify where the new interval should be inserted to maintain order. After insertion, we'll iterate over the array and merge overlapping intervals.
Time Complexity: O(n), where n is the number of intervals.
Space Complexity: O(n) due to the allocation for the result.
1const insert = (intervals, newInterval) => {
2 const result = [];
3 let i = 0;
4 while (i < intervals.length && intervals[i][1] < newInterval[0])
5 result.push(intervals[i++]);
6 while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
7 newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
8 newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
9 i++;
10 }
11 result.push(newInterval);
12 while (i < intervals.length)
13 result.push(intervals[i++]);
14 return result;
15};The JavaScript solution uses arrays and the push method to build the result set. It iteratively processes the intervals to handle non-overlapping, overlapping, and trailing intervals efficiently.
This approach optimizes finding the insert position using binary search. After inserting the new interval, it merges overlapping intervals. This is slightly more efficient when the intervals list is large.
Time Complexity: O(n), even with binary search (O(log n) for insertion, O(n) for merging).
Space Complexity: O(n), to store the new list of intervals.
1function insert(intervals, newInterval) {
2 function findInsertPosition(arr, target) {
3 let low = 0, high = arr.length;
4 while (low < high) {
5 let mid = Math.floor((low + high) / 2);
6 if (arr[mid][0] < target) low = mid + 1;
7 else high = mid;
8 }
9 return low;
10 }
11
12 const pos = findInsertPosition(intervals, newInterval[0]);
13 intervals.splice(pos, 0, newInterval);
14 const result = [intervals[0]];
15 for (let i = 1; i < intervals.length; i++) {
16 const last = result[result.length - 1];
17 if (last[1] >= intervals[i][0])
18 last[1] = Math.max(last[1], intervals[i][1]);
19 else
20 result.push(intervals[i]);
21 }
22 return result;
23}JavaScript provides dynamic arrays and efficient mutation methods enabling binaries to precisely adjust within the provided intervals before merging proceeds uncomplicatedly.