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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
6 vector<vector<int>> result;
7 size_t i = 0;
8 while (i < intervals.size() && intervals[i][1] < newInterval[0])
9 result.push_back(intervals[i++]);
10 while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
11 newInterval[0] = min(newInterval[0], intervals[i][0]);
12 newInterval[1] = max(newInterval[1], intervals[i][1]);
13 i++;
14 }
15 result.push_back(newInterval);
16 while (i < intervals.size())
17 result.push_back(intervals[i++]);
18 return result;
19}The C++ solution uses two main loops: The first loop adds intervals that do not overlap (end before the new interval's start), and the second merges overlapping intervals. After merging, the rest of the intervals are appended.
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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class IntervalInsertion {
5 public int[][] insert(int[][] intervals, int[] newInterval) {
6 int pos = binarySearchPosition(intervals, newInterval[0]);
7 int[][] newIntervals = new int[intervals.length + 1][2];
8 System.arraycopy(intervals, 0, newIntervals, 0, pos);
9 newIntervals[pos] = newInterval;
10 System.arraycopy(intervals, pos, newIntervals, pos + 1, intervals.length - pos);
11 List<int[]> merged = new ArrayList<>();
12 merged.add(newIntervals[0]);
13 for (int i = 1; i < newIntervals.length; i++) {
14 int[] last = merged.get(merged.size() - 1);
15 if (last[1] < newIntervals[i][0])
16 merged.add(newIntervals[i]);
17 else
18 last[1] = Math.max(last[1], newIntervals[i][1]);
19 }
20 return merged.toArray(new int[merged.size()][]);
21 }
22
23 private int binarySearchPosition(int[][] intervals, int start) {
24 int low = 0, high = intervals.length;
25 while (low < high) {
26 int mid = low + (high - low) / 2;
27 if (intervals[mid][0] < start)
28 low = mid + 1;
29 else
30 high = mid;
31 }
32 return low;
33 }
34}This Java solution takes advantage of binary searching and array copying to arrange intervals more efficiently pre-merge, leveraging a helper function to locate the precise index.