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.
1def insert(intervals, newInterval):
2 result = []
3 i = 0
4 while i < len(intervals) and intervals[i][1] < newInterval[0]:
5 result.append(intervals[i])
6 i += 1
7 while i < len(intervals) and intervals[i][0] <= newInterval[1]:
8 newInterval[0] = min(newInterval[0], intervals[i][0])
9 newInterval[1] = max(newInterval[1], intervals[i][1])
10 i += 1
11 result.append(newInterval)
12 while i < len(intervals):
13 result.append(intervals[i])
14 i += 1
15 return result
16The Python solution leverages the dynamic nature of lists. It loops through the given intervals and processes them based on their relation to the new interval, producing a merged list of intervals.
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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int findPosition(const vector<vector<int>>& intervals, int start) {
6 int low = 0, high = intervals.size();
7 while (low < high) {
8 int mid = low + (high - low) / 2;
9 if (intervals[mid][0] < start)
10 low = mid + 1;
11 else
12 high = mid;
13 }
14 return low;
15}
16
17vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
18 int pos = findPosition(intervals, newInterval[0]);
19 intervals.insert(intervals.begin() + pos, newInterval);
20 vector<vector<int>> result = {intervals[0]};
21 for (int i = 1; i < intervals.size(); ++i) {
22 if (result.back()[1] < intervals[i][0])
23 result.push_back(intervals[i]);
24 else
25 result.back()[1] = max(result.back()[1], intervals[i][1]);
26 }
27 return result;
28}The C++ code uses binary search to determine the insertion position in logarithmic time, allowing for intervals to be inserted right before overlapping is assessed. Merging logic remains similar.