Insert Interval into Sorted List in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal when inserting an interval into a sorted list of intervals?

To add the new interval into the list so that the list remains sorted and any overlapping intervals are merged into one.

beginner

How do you know if two intervals overlap?

Two intervals overlap if the start of one interval is less than or equal to the end of the other interval, and vice versa.

beginner

In Rust, which data structure is commonly used to represent an interval?

A tuple of two integers, for example (start, end), where start ≤ end.

intermediate

Why is it important to keep the list of intervals sorted when inserting a new interval?

Because it allows efficient merging and ensures the intervals are in order, which simplifies searching and insertion.

intermediate

What is the time complexity of inserting an interval into a sorted list and merging overlaps?

O(n), where n is the number of intervals, because you may need to check and merge intervals linearly.

What should you do if the new interval does not overlap with any existing intervals?

A Discard the new interval.

B Insert it in the correct sorted position without merging.

C Merge it with the first interval.

D Replace the last interval with the new one.

If there is no overlap, simply insert the new interval where it fits to keep the list sorted.

Which condition indicates two intervals (a, b) and (c, d) overlap?

A b < c

B a > d

C a == d

D b >= c and a <= d

Intervals overlap if the end of the first is at least the start of the second and the start of the first is at most the end of the second.

What is the first step when inserting a new interval into a sorted list?

A Find the position where the new interval should be inserted.

B Merge all intervals first.

C Remove all intervals.

D Sort the list again.

You first find where the new interval fits to maintain the sorted order.

After inserting the new interval, what must you do next?

A Merge any overlapping intervals including the new one.

B Sort the entire list again.

C Delete the new interval.

D Reverse the list.

You merge overlapping intervals to keep the list intervals non-overlapping.

What Rust type is best to represent a list of intervals?

A HashMap<i32, i32>

B String

C Vec<(i32, i32)>

D Option<i32>

A vector of tuples is a simple and effective way to store intervals in Rust.

Explain step-by-step how to insert a new interval into a sorted list of intervals and merge overlaps.

Think about how to keep the list sorted and non-overlapping after insertion.

Describe how to check if two intervals overlap and how to merge them.

Focus on comparing start and end points.

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