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.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. Sort the list again after insertion without merging

B. Add the new interval at the end without merging

C. Remove all intervals that come before the new interval

D. Merge overlapping intervals and keep the list sorted

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Determine the correct insertion approach

   We must merge any overlapping intervals with the new one and keep the list sorted to maintain the property.

3. Final Answer:

   Merge overlapping intervals and keep the list sorted -> Option D

4. Quick Check:

   Insert interval = merge + sort [OK]

Hint: Always merge overlaps to keep intervals sorted and non-overlapping [OK]

Common Mistakes:

• Inserting without merging causes overlaps
• Appending at the end breaks sorting
• Removing intervals unnecessarily

2. Which of the following C code snippets correctly declares a structure for an interval with start and end integers?

easy

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

B. struct Interval { int start; int end; };

C. struct { int start; int end; } Interval;

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

Solution

1. Step 1: Understand C struct typedef syntax

   To define a struct and typedef it simultaneously, use: typedef struct Name { ... } Name;

2. Step 2: Match the correct syntax

   typedef struct Interval { int start; int end; } Interval; uses typedef struct Interval { int start; int end; } Interval; which is correct.

3. Final Answer:

   typedef struct Interval { int start; int end; } Interval; -> Option A

4. Quick Check:

   typedef struct Name { ... } Name; = typedef struct Interval { int start; int end; } Interval; [OK]

Hint: Use typedef struct Name { ... } Name; for clean interval type [OK]

Common Mistakes:

• Missing typedef keyword
• Incorrect struct declaration without name
• Declaring variable instead of type

3. Given the sorted intervals: [[1,3], [6,9]] and a new interval [2,5], what will be the resulting list after insertion and merging?

medium

A. [[1,5], [6,9]]

B. [[1,3], [2,5], [6,9]]

C. [[2,5], [6,9]]

D. [[1,3], [6,9], [2,5]]

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2,5] overlaps with [1,3] because 2 ≤ 3.

2. Step 2: Merge overlapping intervals

   Merge [1,3] and [2,5] into [1,5]. The interval [6,9] remains unchanged.

3. Final Answer:

   [[1,5], [6,9]] -> Option A

4. Quick Check:

   Merge [1,3] & [2,5] = [1,5] [OK]

Hint: Merge intervals if new start ≤ current end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Inserting new interval without sorting
• Appending new interval at wrong position

4. Consider this buggy C code snippet to insert an interval into a sorted list. What is the main error?

void insertInterval(Interval* intervals, int* size, Interval newInterval) {
    int i = 0;
    while (i < *size && intervals[i].end < newInterval.start) {
        i++;
    }
    intervals[i] = newInterval; // Bug here
    (*size)++;
}

medium

A. Increments size before insertion

B. Does not check for overlapping intervals

C. Overwrites an existing interval without shifting elements

D. Uses wrong comparison operator in while loop

Solution

1. Step 1: Analyze insertion logic

   The code finds position i but directly overwrites intervals[i] without moving later intervals.

2. Step 2: Identify the error impact

   Overwriting causes loss of data and corrupts the list. Proper insertion requires shifting elements right.

3. Final Answer:

   Overwrites an existing interval without shifting elements -> Option C

4. Quick Check:

   Overwrite without shift = data loss [OK]

Hint: Shift elements right before inserting new interval [OK]

Common Mistakes:

• Ignoring element shifting
• Not handling overlaps
• Incorrect loop conditions

5. You have intervals [[1,2], [3,5], [6,7], [8,10], [12,16]] and want to insert [4,8]. What is the final list after insertion and merging?

hard

A. [[1,2], [4,8], [12,16]]

B. [[1,2], [3,10], [12,16]]

C. [[1,2], [3,5], [4,8], [6,7], [8,10], [12,16]]

D. [[1,2], [3,8], [12,16]]

Solution

1. Step 1: Find intervals overlapping with [4,8]

   Intervals [3,5], [6,7], and [8,10] overlap with [4,8].

2. Step 2: Merge all overlapping intervals

   Merge [3,5], [6,7], [8,10], and [4,8] into [3,10].

3. Step 3: Construct final list

   Keep [1,2] and [12,16] unchanged. Final list: [[1,2], [3,10], [12,16]].

4. Final Answer:

   [[1,2], [3,10], [12,16]] -> Option B

5. Quick Check:

   Merge overlapping intervals = [3,10] [OK]

Hint: Merge all intervals overlapping new interval into one [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Inserting without merging
• Removing intervals incorrectly