Insert Interval into Sorted List in DSA C - Build from Scratch

Insert Interval into Sorted List

📖 Scenario: You are managing a schedule of booked time slots represented as intervals. Each interval is a pair of start and end times. The schedule is sorted by start times and has no overlapping intervals.Now, you want to add a new time slot to this schedule. You need to insert this new interval into the list and merge any overlapping intervals to keep the schedule clean and sorted.

🎯 Goal: Build a program that inserts a new interval into a sorted list of non-overlapping intervals and merges any overlapping intervals. The final output should show the updated list of intervals.

📋 What You'll Learn

Create an array of intervals called intervals with these exact values: {1, 3}, {6, 9}

Create a new interval called newInterval with the exact values: {2, 5}

Write a function insertInterval that takes the intervals array, its size, the newInterval, and returns the updated intervals with merged overlaps

Print the updated intervals in the format: [start, end] separated by spaces

💡 Why This Matters

🌍 Real World

Managing meeting schedules, booking systems, or time slots where intervals must be merged and kept sorted.

💼 Career

Understanding interval merging is useful in calendar apps, resource allocation, and event planning software development.

1

Create the initial intervals array

Create an array of intervals called intervals with these exact values: {1, 3} and {6, 9}. Also create an integer intervalsSize set to 2.

DSA C

# Your code here

Hint

Use a 2D array to store intervals. Each interval has a start and end.

2

Create the new interval to insert

Create an array called newInterval with the exact values {2, 5}.

DSA C

#include 

int intervals[2][2] = {{1, 3}, {6, 9}};
int intervalsSize = 2;

# Your code here

Hint

Use a simple array of two integers for the new interval.

3

Write the insertInterval function

Write a function called insertInterval that takes intervals, intervalsSize, newInterval, and an output array result. It should merge the newInterval into intervals and store the merged intervals in result. Return the new size of result. Use variables i, index, and n inside the function.

DSA C

#include 

int intervals[2][2] = {{1, 3}, {6, 9}};
int intervalsSize = 2;

int newInterval[2] = {2, 5};

// Your code here

Hint

Use three loops: one to add intervals before newInterval, one to merge overlaps, and one to add intervals after.

4

Print the updated intervals

Create an array result with size 10 by 2. Call insertInterval with intervals, intervalsSize, newInterval, and result. Store the returned size in newSize. Then print each interval in result in the format [start, end] separated by spaces.

DSA C

#include 

int intervals[2][2] = {{1, 3}, {6, 9}};
int intervalsSize = 2;

int newInterval[2] = {2, 5};

int insertInterval(int intervals[][2], int intervalsSize, int newInterval[2], int result[][2]) {
    int i = 0, index = 0, n = intervalsSize;

    // Add all intervals ending before newInterval starts
    while (i  newInterval[1])
            newInterval[1] = intervals[i][1];
        i++;
    }

    // Add the merged newInterval
    result[index][0] = newInterval[0];
    result[index][1] = newInterval[1];
    index++;

    // Add remaining intervals
    while (i < n) {
        result[index][0] = intervals[i][0];
        result[index][1] = intervals[i][1];
        i++;
        index++;
    }

    return index;
}

// Your code here

Hint

Call the function and print each interval in the result array.