Insert Interval into Sorted List in DSA C

Mental Model

We add a new time slot into a list of sorted time slots, merging any that overlap so the list stays sorted and without overlaps.

Analogy: Imagine you have a schedule with booked meeting times sorted by start time. You want to add a new meeting. If it overlaps with existing meetings, you merge them into one longer meeting to avoid conflicts.

Intervals: [1,3] -> [6,9] -> null
New interval: [2,5]
Goal: Insert and merge overlapping intervals

Dry Run Walkthrough

Input: list: [1,3] -> [6,9], insert [2,5]

Goal: Insert [2,5] into the sorted list and merge overlapping intervals

Step 1: Start with empty result list, pointer at first interval [1,3]

[1,3] -> [6,9] -> null
New interval: [2,5]

Why: We need to compare new interval with existing intervals

Step 2: Check if current interval [1,3] ends before new interval starts (3 < 2)? No, so overlap possible

[1,3] -> [6,9] -> null
New interval: [2,5]

Why: Intervals overlap, so we merge

Step 3: Merge intervals: new start = min(1,2)=1, new end = max(3,5)=5; update new interval to [1,5]

Merged new interval: [1,5]
Remaining intervals: [6,9]

Why: Merging overlapping intervals keeps list sorted and non-overlapping

Step 4: Move to next interval [6,9], check if it ends before new interval starts (9 < 1)? No, check if it starts after new interval ends (6 > 5)? Yes

Merged new interval: [1,5]
Next interval: [6,9]

Why: No overlap, so we can add new interval before [6,9]

Step 5: Add merged new interval [1,5] to result list

Result: [1,5]

Why: We add the merged interval before intervals that start after it

Step 6: Add remaining interval [6,9] to result list

Result: [1,5] -> [6,9] -> null

Why: Add all remaining intervals after new interval

Result:

Final list: [1,5] -> [6,9] -> null

Annotated Code

DSA C

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

// Define interval node
typedef struct Interval {
    int start;
    int end;
    struct Interval* next;
} Interval;

// Create new interval node
Interval* newInterval(int start, int end) {
    Interval* node = (Interval*)malloc(sizeof(Interval));
    node->start = start;
    node->end = end;
    node->next = NULL;
    return node;
}

// Insert interval into sorted list and merge overlaps
Interval* insertInterval(Interval* head, Interval* newInt) {
    Interval dummy = {0, 0, NULL};
    Interval* tail = &dummy;
    Interval* curr = head;

    // Add all intervals ending before new interval starts
    while (curr && curr->end < newInt->start) {
        tail->next = curr;
        tail = curr;
        curr = curr->next;
    }

    // Merge overlapping intervals
    while (curr && curr->start <= newInt->end) {
        if (curr->start < newInt->start) newInt->start = curr->start;
        if (curr->end > newInt->end) newInt->end = curr->end;
        curr = curr->next;
    }

    // Add merged new interval
    tail->next = newInt;
    tail = newInt;

    // Add remaining intervals
    tail->next = curr;

    return dummy.next;
}

// Print intervals
void printIntervals(Interval* head) {
    Interval* curr = head;
    while (curr) {
        printf("[%d,%d]", curr->start, curr->end);
        if (curr->next) printf(" -> ");
        curr = curr->next;
    }
    printf(" -> null\n");
}

int main() {
    // Create list: [1,3] -> [6,9]
    Interval* head = newInterval(1,3);
    head->next = newInterval(6,9);

    // New interval to insert: [2,5]
    Interval* newInt = newInterval(2,5);

    // Insert and merge
    Interval* result = insertInterval(head, newInt);

    // Print result
    printIntervals(result);
    return 0;
}

while (curr && curr->end < newInt->start) {

Add intervals that end before new interval starts

while (curr && curr->start <= newInt->end) {

Merge all intervals overlapping with new interval

if (curr->start < newInt->start) newInt->start = curr->start;

Update new interval start to earliest start

if (curr->end > newInt->end) newInt->end = curr->end;

Update new interval end to latest end

tail->next = newInt;

Add merged new interval to result list

tail->next = curr;

Add remaining intervals after merged interval

Output

[1,5] -> [6,9] -> null

Complexity Analysis

Time: O(n) because we traverse the list once to insert and merge intervals

Space: O(1) because we modify the list in place without extra data structures

vs Alternative: Compared to creating a new list and sorting, this approach is more efficient as it uses the sorted property and merges in one pass

Edge Cases

Empty list

New interval becomes the only interval in the list

DSA C

while (curr && curr->end < newInt->start) {

New interval does not overlap and is before all intervals

New interval is added at the front

DSA C

while (curr && curr->end < newInt->start) {

New interval overlaps all intervals

All intervals merge into one big interval

DSA C

while (curr && curr->start <= newInt->end) {

When to Use This Pattern

When you see a problem about inserting and merging intervals in a sorted list, use the merge intervals pattern to combine overlapping intervals efficiently.

Common Mistakes

Mistake: Not merging overlapping intervals and just inserting new interval
Fix: Check for overlaps and merge intervals by updating start and end boundaries

Mistake: Not handling intervals before new interval correctly
Fix: Add all intervals that end before new interval starts before merging

Summary

Inserts a new interval into a sorted list of intervals and merges any overlaps.

Use when you need to add a time slot into a schedule without conflicts.

The key is to merge overlapping intervals by adjusting start and end boundaries while traversing once.

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