Insert Interval into Sorted List in DSA Rust

Mental Model

We add a new time range into a list of sorted, non-overlapping time ranges, merging any that overlap.

Analogy: Imagine booking a meeting room with existing reserved time slots. When you add a new meeting, you combine overlapping times so the schedule stays neat and sorted.

Intervals list:
[1,3] -> [6,9] -> null
Insert interval:
[2,5]

Dry Run Walkthrough

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

Goal: Insert [2,5] into the sorted list and merge overlapping intervals to keep the list sorted and non-overlapping.

Step 1: Check first interval [1,3] against [2,5], they overlap so merge to [1,5]

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

Why: We merge overlapping intervals to keep the list non-overlapping.

Step 2: Check next interval [6,9], no overlap with [1,5], keep as is

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

Why: No overlap means we keep intervals separate.

Step 3: Insert merged interval list as final result

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

Why: The list is sorted and merged correctly.

Result:

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

Annotated Code

DSA Rust

use std::cmp::{min, max};

#[derive(Debug, Clone)]
struct Interval {
    start: i32,
    end: i32,
}

fn insert_interval(intervals: Vec<Interval>, new_interval: Interval) -> Vec<Interval> {
    let mut result = Vec::new();
    let mut i = 0;
    let n = intervals.len();
    let mut new_start = new_interval.start;
    let mut new_end = new_interval.end;

    // Add all intervals ending before new_interval starts
    while i < n && intervals[i].end < new_start {
        result.push(intervals[i].clone());
        i += 1;
    }

    // Merge overlapping intervals
    while i < n && intervals[i].start <= new_end {
        new_start = min(new_start, intervals[i].start);
        new_end = max(new_end, intervals[i].end);
        i += 1;
    }

    // Add the merged interval
    result.push(Interval { start: new_start, end: new_end });

    // Add remaining intervals
    while i < n {
        result.push(intervals[i].clone());
        i += 1;
    }

    result
}

fn print_intervals(intervals: &Vec<Interval>) {
    for interval in intervals {
        print!("[{},{}] -> ", interval.start, interval.end);
    }
    println!("null");
}

fn main() {
    let intervals = vec![
        Interval { start: 1, end: 3 },
        Interval { start: 6, end: 9 },
    ];
    let new_interval = Interval { start: 2, end: 5 };

    let merged = insert_interval(intervals, new_interval);
    print_intervals(&merged);
}

while i < n && intervals[i].end < new_start {

Add intervals that end before new interval starts -- no overlap

while i < n && intervals[i].start <= new_end {

Merge all intervals overlapping with new interval

result.push(Interval { start: new_start, end: new_end });

Add the merged interval to result

while i < n {

Add remaining intervals after merged interval

Output

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

Complexity Analysis

Time: O(n) because we scan the list of intervals once

Space: O(n) because we create a new list to store merged intervals

vs Alternative: Naive approach might insert and then sort or merge repeatedly, costing O(n log n) or more

Edge Cases

Empty intervals list

Returns list with only the new interval

DSA Rust

while i < n && intervals[i].end < new_start {

New interval before all existing intervals

New interval is added at the start without merges

DSA Rust

while i < n && intervals[i].end < new_start {

New interval after all existing intervals

New interval is added at the end without merges

DSA Rust

while i < n {

New interval overlaps multiple intervals

All overlapping intervals merged into one

DSA Rust

while i < n && intervals[i].start <= new_end {

When to Use This Pattern

When you see a problem about adding a new range into sorted non-overlapping ranges, use the insert and merge pattern to keep the list sorted and merged.

Common Mistakes

Mistake: Not merging all overlapping intervals, only merging the first overlap
Fix: Use a loop to merge all intervals overlapping with the new interval

Mistake: Inserting new interval before merging, causing incorrect order
Fix: Merge first, then insert the merged interval into the result

Summary

Inserts a new interval into a sorted list of non-overlapping intervals and merges overlaps.

Use when you need to add a time range into a schedule without overlaps.

The key is to add intervals before, merge overlapping ones, then add intervals after.

Practice

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

easy

A. To remove all intervals that come before the new interval

B. To replace all intervals with the new interval

C. To sort the intervals in descending order

D. To add the new interval and merge any overlapping intervals

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals and want to insert a new interval without breaking the order.

2. Step 2: Identify the required operation

   We must insert the new interval and merge any intervals that overlap with it to keep the list sorted and non-overlapping.

3. Final Answer:

   To add the new interval and merge any overlapping intervals -> Option D

4. Quick Check:

   Insert and merge intervals = To add the new interval and merge any overlapping intervals [OK]

Hint: Insert and merge overlapping intervals to keep list sorted [OK]

Common Mistakes:

• Replacing all intervals instead of merging
• Sorting intervals in descending order
• Removing intervals before the new one

2. Which Rust syntax correctly declares a vector of intervals where each interval is a tuple of two integers?

easy

A. let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)];

B. let intervals = [(1, 3), (6, 9)];

C. let intervals: Vec<[i32; 2]> = vec![[1, 3], [6, 9]];

D. let intervals: Vec<(int, int)> = vec![(1, 3), (6, 9)];

Solution

1. Step 1: Identify correct Rust tuple and vector syntax

   Rust uses (i32, i32) for tuple of two integers and Vec for vector type.

2. Step 2: Check each option

   let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)]; uses Vec<(i32, i32)> with vec! macro and tuples correctly. let intervals = [(1, 3), (6, 9)]; is an array, not a vector. let intervals: Vec<[i32; 2]> = vec![[1, 3], [6, 9]]; uses arrays inside vector, which is valid but different type. let intervals: Vec<(int, int)> = vec![(1, 3), (6, 9)]; uses 'int' which is invalid in Rust.

3. Final Answer:

   let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)]; -> Option A

4. Quick Check:

   Correct Rust tuple vector syntax = let intervals: Vec<(i32, i32)> = vec![(1, 3), (6, 9)]; [OK]

Hint: Use Vec<(i32, i32)> and vec! macro for interval list [OK]

Common Mistakes:

• Using 'int' instead of 'i32'
• Confusing arrays and tuples
• Not using vec! macro for vectors

3. Given the intervals vec![(1, 3), (6, 9)] and a new interval (2, 5), what is the resulting list after insertion and merging?

medium

A. [(2, 5), (6, 9)]

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

C. [(1, 5), (6, 9)]

D. [(1, 9)]

Solution

1. Step 1: Insert new interval and find overlaps

   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 C

4. Quick Check:

   Merged intervals = [(1, 5), (6, 9)] [OK]

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

Common Mistakes:

• Not merging overlapping intervals
• Inserting without sorting
• Merging all intervals incorrectly

4. Consider this Rust code snippet for inserting an interval into a sorted list:

fn insert_interval(intervals: &mut Vec<(i32, i32)>, new_interval: (i32, i32)) {
    let mut i = 0;
    while i < intervals.len() {
        if intervals[i].1 < new_interval.0 {
            i += 1;
        } else if intervals[i].0 > new_interval.1 {
            intervals.insert(i, new_interval);
            return;
        } else {
            intervals[i].0 = intervals[i].0.min(new_interval.0);
            intervals[i].1 = intervals[i].1.max(new_interval.1);
            intervals.remove(i + 1);
        }
    }
    intervals.push(new_interval);
}

What is the main bug in this code?

medium

A. It never increments index i inside the else block causing infinite loop

B. It inserts the new interval at the wrong position

C. It removes the wrong interval when merging overlapping intervals

D. It does not handle empty intervals vector

Solution

1. Step 1: Examine the else branch for merging

   The code updates intervals[i] by merging the new interval but never increments the index i inside the else block.

2. Step 2: Identify infinite loop cause

   Because i is not incremented after merging and removing intervals[i+1], the loop can get stuck processing the same index repeatedly, causing an infinite loop.

3. Final Answer:

   It never increments index i inside the else block causing infinite loop -> Option A

4. Quick Check:

   Missing i increment in else block = infinite loop [OK]

Hint: Always increment index after merging to avoid infinite loop [OK]

Common Mistakes:

• Forgetting to increment index after removal
• Assuming insert always works without checks
• Ignoring empty vector edge case

5. You have a sorted list of intervals vec![(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]. Insert the new interval (4, 8) and return the updated list after merging all overlapping intervals.

hard

A. [(1, 2), (3, 16)]

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

C. [(1, 2), (4, 8), (12, 16)]

D. [(1, 2), (3, 5), (6, 8), (8, 10), (12, 16)]

Solution

1. Step 1: Identify intervals overlapping with (4, 8)

   Intervals (3, 5), (6, 7), and (8, 10) overlap with (4, 8) because their ranges intersect.

2. Step 2: Merge all overlapping intervals

   Merge (3, 5), (6, 7), (8, 10), and (4, 8) into one interval (3, 10). The intervals (1, 2) and (12, 16) remain unchanged.

3. Final Answer:

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

4. Quick Check:

   Merged intervals after insertion = [(1, 2), (3, 10), (12, 16)] [OK]

Hint: Merge all intervals overlapping new interval's range [OK]

Common Mistakes:

• Merging only partially overlapping intervals
• Not merging intervals that touch at boundaries
• Replacing intervals incorrectly