Insert Interval - C Solution

1. Introduction

In this post, we explore a common problem in interval manipulation known as "Insert Interval". This problem involves inserting a new interval into a list of non-overlapping intervals sorted by their start times, and merging any overlapping intervals as necessary. It's an excellent exercise in array manipulation and interval merging in C programming.

Problem

Given an array of non-overlapping intervals sorted by their start times, and a new interval, the task is to insert the new interval into the array such that the array remains sorted and merge any overlapping intervals. The goal is to return the array after the insertion of the new interval.

2. Solution Steps

1. Initialize a dynamic array to store the merged intervals.

2. Iterate through the original intervals.

3. If the new interval does not overlap with the current interval, add the current interval to the result.

4. If it overlaps, merge the new interval with the current interval.

5. After processing all intervals, add the remaining new interval to the result.

6. Return the merged intervals array.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Interval;

// Function to insert and merge intervals
Interval* insert(Interval* intervals, int intervalsSize, Interval newInterval, int* returnSize) {
    Interval* result = (Interval*)malloc((intervalsSize + 1) * sizeof(Interval));
    *returnSize = 0;
    int i = 0;

    // Add all intervals before the new interval
    while (i < intervalsSize && intervals[i].end < newInterval.start) {
        result[(*returnSize)++] = intervals[i++];
    }

    // Merge the new interval
    while (i < intervalsSize && intervals[i].start <= newInterval.end) {
        newInterval.start = newInterval.start < intervals[i].start ? newInterval.start : intervals[i].start;
        newInterval.end = newInterval.end > intervals[i].end ? newInterval.end : intervals[i].end;
        i++;
    }
    result[(*returnSize)++] = newInterval;

    // Add the remaining intervals
    while (i < intervalsSize) {
        result[(*returnSize)++] = intervals[i++];
    }

    return result;
}

// Main function to test the insert function
int main() {
    Interval intervals[] = {{1, 3}, {6, 9}};
    Interval newInterval = {2, 5};
    int returnSize;
    Interval* merged = insert(intervals, 2, newInterval, &returnSize);

    printf("Merged Intervals: ");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d] ", merged[i].start, merged[i].end);
    }
    free(merged);

    return 0;
}

Output:

Merged Intervals: [1,5] [6,9]

Explanation:

1. The function insert creates a dynamic array to store the result.

2. Iterates through existing intervals and adds non-overlapping ones to the result.

3. Merges overlapping intervals with the new interval.

4. Adds remaining intervals after the new interval.

5. The main function demonstrates the usage with an example, prints the merged intervals, and frees the allocated memory.