Dare2Solve
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.
Initialization: Create two lists, left
and right
, 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:
left
list.right
list.Combine Results: After processing all intervals, the left
list contains all intervals before the new merged interval, and the right
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.
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.
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.
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int start = newInterval[0];
int end = newInterval[1];
vector<vector<int>> 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;
}
};
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
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int start = newInterval[0];
int end = newInterval[1];
List<int[]> left = new ArrayList<>();
List<int[]> 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<int[]> result = new ArrayList<>(left);
result.add(new int[]{start, end});
result.addAll(right);
return result.toArray(new int[result.size()][]);
}
}
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];
};