🎨Now live: Try our Free AI Image Generation Feature

Intuition
Given a list of non-overlapping intervals sorted by their start times and a new interval, the task is to insert the new interval into the list and merge any overlapping intervals. The list should remain sorted and non-overlapping after the insertion.
Approach
- Initialization: Create two lists,
left
andright
, to store intervals that are completely to the left and right of the new interval, respectively. - Iterate Through Intervals: Traverse the given list of intervals:
- If the current interval ends before the new interval starts, it belongs to the
left
list. - If the current interval starts after the new interval ends, it belongs to theright
list. - If there is an overlap, merge the intervals by updating the start to the minimum start and the end to the maximum end. - Combine Results: After processing all intervals, the
left
list contains all intervals before the new merged interval, and theright
list contains all intervals after the new merged interval. Combine these lists with the new merged interval in between. - Return Result: Return the combined list of intervals.
Complexity
Time Complexity:
O(n), where n is the number of intervals. The list is traversed once to place intervals in left
and right
lists and merge overlaps.
Space Complexity:
O(n) for the additional lists left
and right
, where n is the number of intervals. The space used for the result is proportional to the number of intervals.
Code
C++
class Solution {
public:
vector> insert(vector>& intervals, vector& newInterval) {
int start = newInterval[0];
int end = newInterval[1];
vector> left, right;
for (const auto& interval : intervals) {
int first = interval[0];
int last = interval[1];
if (last < start) {
left.push_back(interval);
} else if (first > end) {
right.push_back(interval);
} else {
start = min(start, first);
end = max(end, last);
}
}
left.push_back({start, end});
left.insert(left.end(), right.begin(), right.end());
return left;
}
};
Python
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
start, end = newInterval
left, right = [], []
for first, last in intervals:
if last < start:
left.append([first, last])
elif first > end:
right.append([first, last])
else:
start = min(start, first)
end = max(end, last)
return left + [[start, end]] + right
Java
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int start = newInterval[0];
int end = newInterval[1];
List left = new ArrayList<>();
List right = new ArrayList<>();
for (int[] interval : intervals) {
int first = interval[0];
int last = interval[1];
if (last < start) {
left.add(interval);
} else if (first > end) {
right.add(interval);
} else {
start = Math.min(start, first);
end = Math.max(end, last);
}
}
List result = new ArrayList<>(left);
result.add(new int[]{start, end});
result.addAll(right);
return result.toArray(new int[result.size()][]);
}
}
JavaScript
var insert = function (intervals, newInterval) {
let [start, end] = newInterval;
let left = [];
let right = [];
for (const interval of intervals) {
const [first, last] = interval;
if (last < start) left.push(interval);
else if (first > end) right.push(interval);
else {
start = Math.min(start, first);
end = Math.max(end, last);
}
}
return [...left, [start, end], ...right];
};