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 <stdio.h>
2#include <stdlib.h>
3
4struct Interval {
5 int start;
6 int end;
7};
8
9struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
10 struct Interval* result = malloc(sizeof(struct Interval) * (intervalsSize + 1));
11 int i, j = 0;
12 for (i = 0; i < intervalsSize && intervals[i].end < newInterval.start; ++i) {
13 result[j++] = intervals[i];
14 }
15 for (; i < intervalsSize && intervals[i].start <= newInterval.end; ++i) {
16 newInterval.start = fmin(newInterval.start, intervals[i].start);
17 newInterval.end = fmax(newInterval.end, intervals[i].end);
18 }
19 result[j++] = newInterval;
20 while (i < intervalsSize) {
21 result[j++] = intervals[i++];
22 }
23 *returnSize = j;
24 return result;
25}The C solution allocates memory for a new set of intervals that can hold the original intervals plus the new one. It adds all the intervals that end before the new interval's start. Next, it merges overlapping intervals with the new interval. Finally, all remaining intervals are appended after the merged intervals. The function returns the new 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 <stdio.h>
2#include <stdlib.h>
3
4int binarySearch(int** intervals, int size, int target) {
5 int low = 0, high = size - 1;
6 while (low <= high) {
7 int mid = low + (high - low) / 2;
8 if (intervals[mid][0] == target)
9 return mid;
10 else if (intervals[mid][0] < target)
11 low = mid + 1;
12 else
13 high = mid - 1;
14 }
15 return low;
16}
17
18int** insert(int** intervals, int intervalsSize, int* newInterval, int newIntervalSize, int* returnSize) {
19 int pos = binarySearch(intervals, intervalsSize, newInterval[0]);
20 int** result = (int**)malloc(sizeof(int*) * (intervalsSize + 1));
21 int k = 0;
22 for (int i = 0; i < pos; i++) {
23 result[k] = (int*)malloc(sizeof(int) * 2);
24 result[k][0] = intervals[i][0];
25 result[k++][1] = intervals[i][1];
26 }
27 int* mergedInterval = malloc(sizeof(int) * 2);
28 mergedInterval[0] = newInterval[0];
29 mergedInterval[1] = newInterval[1];
30 while (pos < intervalsSize && intervals[pos][0] <= mergedInterval[1]) {
31 mergedInterval[0] = fmin(mergedInterval[0], intervals[pos][0]);
32 mergedInterval[1] = fmax(mergedInterval[1], intervals[pos][1]);
33 pos++;
34 }
35 result[k++] = mergedInterval;
36 while (pos < intervalsSize) {
37 result[k] = (int*)malloc(sizeof(int) * 2);
38 result[k][0] = intervals[pos][0];
39 result[k++][1] = intervals[pos][1];
40 pos++;
41 }
42 *returnSize = k;
43 return result;
44}This C solution integrates binary search to locate the accurate insertion index for the new interval before merging. Although binary search optimizes finding the position, the merge process remains linear.