#include <stdio.h>
#include <stdlib.h>
typedef struct {
int start;
int end;
} Interval;
// Append an interval to a dynamic array
void append(Interval **arr, int *size, int *capacity, Interval iv) {
if (*size >= *capacity) {
*capacity *= 2;
*arr = realloc(*arr, (*capacity) * sizeof(Interval));
}
(*arr)[(*size)++] = iv;
}
Interval* insertInterval(Interval *intervals, int n, Interval newInterval, int *outSize) {
int i = 0;
// Allocate result array
int capacity = n + 1;
Interval *result = malloc(capacity * sizeof(Interval));
*outSize = 0;
// 1. Add all intervals that end BEFORE the new interval starts.
// These cannot overlap.
while (i < n && intervals[i].end < newInterval.start) {
append(&result, outSize, &capacity, intervals[i]);
i++;
}
// 2. Merge all intervals that DO overlap with the new interval.
// Overlap condition: intervals[i].start <= newInterval.end
while (i < n && intervals[i].start <= newInterval.end) {
if (intervals[i].start < newInterval.start)
newInterval.start = intervals[i].start;
if (intervals[i].end > newInterval.end)
newInterval.end = intervals[i].end;
i++;
}
// Add the merged interval
append(&result, outSize, &capacity, newInterval);
// 3. Add all remaining intervals (those starting AFTER new interval ends)
while (i < n) {
append(&result, outSize, &capacity, intervals[i]);
i++;
}
return result;
}
int main() {
Interval intervals[] = {
{1, 3},
{6, 8},
{13, 18}
};
int size = sizeof(intervals) / sizeof(intervals[0]);
Interval newInterval1 = {9, 11};
int size1;
Interval *updated = insertInterval(intervals, size, newInterval1, &size1);
Interval newInterval2 = {2, 5};
int size2;
Interval *updated2 = insertInterval(updated, size1, newInterval2, &size2);
printf("Updated intervals:\n");
for (int i = 0; i < size2; i++) {
printf("[%d,%d] ", updated2[i].start, updated2[i].end);
}
free(updated);
free(updated2);
return 0;
}
/*
run:
Updated intervals:
[1,5] [6,8] [9,11] [13,18]
*/
