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.