Problem Statement:
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval 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 starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note: that you don’t need to modify intervals in-place. You can make a new array and return it.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
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 <= 3 * 104intervals[i].length == 20 <= starti <= endi <= 105intervalsis sorted bystarti in ascending order.newInterval.length == 20 <= start <= end <= 105
Approach:
Add intervals before xPush allintervalsending before x starts (i.e., arr[i][1] < x[0]).- Merge overlapping intervals with x: While intervals overlap
(arr[i][0] <= x[1]), expand x by updating: - x[0] = min(x[0], arr[i][0])
- x[1] = max(x[1], arr[i][1])
Insertmerged interval x: Push the merged interval into result.- Add remaining intervals: Push all
intervalsthat come after x.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(n)
Dry Run
Input: arr = [[1,3],[6,9]], x = [2,5]
Step 0: Start
- Function: insert(arr, x)
- arr = [[1,3], [6,9]]
- x = [2,5]
- n = arr.length = 2
- ans = []
- i = 0
Step 1: First while loop → while (i < n && arr[i][1] < x[0])
- arr[0][1] = 3, x[0] = 2
- Check: 3 < 2 ? → false
→ Exit first while (no intervals added)
State after Step 1:
- ans = []
- i = 0
- x = [2,5]
Step 2: Second while loop → while (i < n && arr[i][0] <= x[1])
Iteration 1 (i = 0):
- arr[0] = [1,3]
- Check: 1 <= 5 ? → true (overlap)
- Update x:
x[0] = min(2,1) = 1
x[1] = max(5,3) = 5
- New x = [1,5]
- i = 1
Iteration 2 (i = 1):
- arr[1][0] = 6, x[1] = 5
- Check: 6 <= 5 ? → false
→ Exit second while
State after Step 2:
- ans = []
- i = 1
- x = [1,5]
Step 3: Push merged x
- ans.push(x) → ans = [[1,5]]
Step 4: Third while loop → while (i < n)
Iteration 1 (i = 1):
- ans.push(arr[1]) → ans = [[1,5], [6,9]]
- i = 2
i = 2 == n → loop ends
Step 5: End
- Final ans = [[1,5], [6,9]]
Explanation:
- Interval [1,3] overlapped with x = [2,5], merged into [1,5].
- Interval [6,9] didn’t overlap, so kept as is.
Output: [[1,5],[6,9]]
var insert = function(arr, x) {
let n = arr.length;
let ans = [];
let i = 0;
while(i < n && arr[i][1] < x[0]) {
ans.push(arr[i]);
++i;
}
while(i < n && arr[i][0] <= x[1]){
x[0] = Math.min(x[0], arr[i][0]);
x[1] = Math.max(x[1], arr[i][1]);
++i;
}
ans.push(x);
while(i < n){
ans.push(arr[i]);
++i;
}
return ans;
};
def insert(arr, x):
"""
arr: list of [start, end], sorted and non-overlapping
x: [start, end]
returns: new list of intervals after inserting x
"""
n = len(arr)
ans = []
i = 0
while i < n and arr[i][1] < x[0]:
ans.append(arr[i])
i += 1
while i < n and arr[i][0] <= x[1]:
x[0] = min(x[0], arr[i][0])
x[1] = max(x[1], arr[i][1])
i += 1
ans.append(x)
while i < n:
ans.append(arr[i])
i += 1
return ans
import java.util.*;
public class Intervals {
public static List insert(List arr, int[] x) {
int n = arr.size();
List ans = new ArrayList<>();
int i = 0;
while (i < n && arr.get(i)[1] < x[0]) {
ans.add(arr.get(i));
++i;
}
while (i < n && arr.get(i)[0] <= x[1]) {
x[0] = Math.min(x[0], arr.get(i)[0]);
x[1] = Math.max(x[1], arr.get(i)[1]);
++i;
}
ans.add(new int[]{x[0], x[1]});
while (i < n) {
ans.add(arr.get(i));
++i;
}
return ans;
}
}
#include <vector>
#include <algorithm>
using namespace std;
vector> insertInterval(const vector>& arr, vector x) {
int n = arr.size();
vector> ans;
int i = 0;
while (i < n && arr[i][1] < x[0]) {
ans.push_back(arr[i]);
++i;
}
while (i < n && arr[i][0] <= x[1]) {
x[0] = min(x[0], arr[i][0]);
x[1] = max(x[1], arr[i][1]);
++i;
}
ans.push_back(x);
while (i < n) {
ans.push_back(arr[i]);
++i;
}
return ans;
}
#include <stdlib.h>
#include <stdio.h>
typedef struct {
int start;
int end;
} Interval;
// arr: pointer to an array of Interval of length n
// x: interval to insert
// returns: newly allocated array of Interval; out_len set to resulting length
Interval* insertInterval(const Interval* arr, int n, Interval x, int* out_len) {
// allocate space for at most n+1 intervals
Interval* ans = (Interval*)malloc((n + 1) * sizeof(Interval));
int idx = 0;
int i = 0;
while (i < n && arr[i].end < x.start) {
ans[idx++] = arr[i];
++i;
}
while (i < n && arr[i].start <= x.end) {
if (arr[i].start < x.start) x.start = arr[i].start;
if (arr[i].end > x.end) x.end = arr[i].end;
++i;
}
ans[idx++] = x;
while (i < n) {
ans[idx++] = arr[i];
++i;
}
ans = (Interval*)realloc(ans, idx * sizeof(Interval));
*out_len = idx;
return ans;
}
using System;
using System.Collections.Generic;
public class Intervals {
// arr: List where each int[] is {start, end}
public static List Insert(List arr, int[] x) {
int n = arr.Count;
List ans = new List();
int i = 0;
while (i < n && arr[i][1] < x[0]) {
ans.Add(arr[i]);
++i;
}
while (i < n && arr[i][0] <= x[1]) {
x[0] = Math.Min(x[0], arr[i][0]);
x[1] = Math.Max(x[1], arr[i][1]);
++i;
}
ans.Add(new int[]{x[0], x[1]});
while (i < n) {
ans.Add(arr[i]);
++i;
}
return ans;
}
}
