Insert Interval into Sorted List in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert the new interval into the list.

DSA C++

intervals.insert(intervals.begin() + [1], newInterval);

Drag options to blanks, or click blank then click option'

Apos

Bi

C0

Dintervals.size()

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or intervals.size() blindly without finding the correct position.

Using an undefined variable like pos.

We insert the new interval at position i, where i is the index found to place the new interval.

2fill in blank

medium

Complete the code to find the correct position to insert the new interval.

DSA C++

while (i < intervals.size() && intervals[i].end < newInterval.start) {
    [1];
}

Drag options to blanks, or click blank then click option'

Ai++

Bi--

Cintervals[i]++

DnewInterval.start++

Attempts:

3 left

💡 Hint

Common Mistakes

Decrementing i which causes an infinite loop.

Trying to increment the interval or newInterval values.

We increment i to move forward until we find the right position where the new interval can be inserted.

3fill in blank

hard

Fix the error in the merging loop condition.

DSA C++

while (i < intervals.size() && intervals[i].start <= [1]) {
    newInterval.start = std::min(newInterval.start, intervals[i].start);
    newInterval.end = std::max(newInterval.end, intervals[i].end);
    intervals.erase(intervals.begin() + i);
}

Drag options to blanks, or click blank then click option'

Aintervals[i].end

BnewInterval.start

Cintervals[i].start

DnewInterval.end

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with newInterval.start instead of newInterval.end.

Comparing with intervals[i].end which is incorrect here.

We merge intervals that start before or at the end of the new interval, so we compare intervals[i].start with newInterval.end.

4fill in blank

hard

Fill both blanks to correctly merge overlapping intervals.

DSA C++

newInterval.start = std::min(newInterval.start, intervals[[1]].start);
newInterval.end = std::max(newInterval.end, intervals[[2]].end);

Drag options to blanks, or click blank then click option'

Ai

Bi - 1

C0

Dintervals.size() - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using different indices for start and end.

Using fixed indices like 0 or intervals.size() - 1.

We use the current index i to update the start and end of newInterval during merging.

5fill in blank

hard

Fill all three blanks to complete the function that inserts and merges intervals.

DSA C++

int i = 0;
while (i < intervals.size() && intervals[i].end < [1]) {
    i++;
}
intervals.insert(intervals.begin() + i, [2]);
while (i + 1 < intervals.size() && intervals[i + 1].start <= [3]) {
    intervals[i].start = std::min(intervals[i].start, intervals[i + 1].start);
    intervals[i].end = std::max(intervals[i].end, intervals[i + 1].end);
    intervals.erase(intervals.begin() + i + 1);
}

Drag options to blanks, or click blank then click option'

AnewInterval.start

BnewInterval

Cintervals[i].end

Dintervals[i].start

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong interval boundaries for comparison.

Inserting wrong object or at wrong position.

We find the position where newInterval.start fits, insert newInterval, then merge overlapping intervals by comparing with intervals[i].end.

Practice

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

easy

A. To merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

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

D. To sort the intervals again after insertion without merging

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals that do not overlap. When inserting a new interval, we must keep the list sorted and merge any overlapping intervals.

2. Step 2: Identify the correct approach

   Simply adding the new interval without merging can cause overlaps. Sorting again without merging breaks the non-overlapping property. Removing intervals before the new one is incorrect.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert Interval = Merge and keep sorted [OK]

Hint: Always merge overlapping intervals after insertion [OK]

Common Mistakes:

• Inserting without merging overlaps
• Sorting intervals again without merging
• Removing intervals unnecessarily

2. Which of the following C++ code snippets correctly declares a vector of intervals where each interval is a pair of integers?

easy

A. std::vector intervals;

B. std::vector intervals;

C. std::vector intervals;

D. std::vector> intervals;

Solution

1. Step 1: Understand vector and pair syntax

   In C++, a vector of pairs is declared as std::vector>. The pair must specify both types inside angle brackets.

2. Step 2: Check each option

   std::vector> intervals; correctly uses std::pair. std::vector intervals; is invalid syntax for vector. std::vector intervals; misses the second type in pair. std::vector intervals; misses template parameters for pair.

3. Final Answer:

   std::vector> intervals; -> Option D

4. Quick Check:

   Vector of pairs syntax = std::vector> intervals; [OK]

Hint: Use std::vector> for intervals [OK]

Common Mistakes:

• Missing template parameters in pair
• Incorrect vector declaration syntax
• Using incomplete pair types

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, 3), (2, 5), (6, 9)]

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

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

D. [(1, 9)]

Solution

1. Step 1: Identify overlapping intervals

   The new interval (2, 5) overlaps with (1, 3) because 2 <= 3. They should be merged into (1, 5).

2. Step 2: Merge and keep other intervals

   After merging (1, 3) and (2, 5) into (1, 5), the interval (6, 9) remains unchanged.

3. Final Answer:

   [(1, 5), (6, 9)] -> Option B

4. Quick Check:

   Merge overlapping 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 the following C++ code snippet for inserting an interval into a sorted list of intervals:

std::vector> insertInterval(std::vector>& intervals, std::pair newInterval) {
    std::vector> result;
    int i = 0;
    while (i < intervals.size() && intervals[i].second < newInterval.first) {
        result.push_back(intervals[i]);
        i++;
    }
    while (i < intervals.size() && intervals[i].first <= newInterval.second) {
        newInterval.first = std::min(newInterval.first, intervals[i].first);
        newInterval.second = std::max(newInterval.second, intervals[i].second);
        i++;
    }
    result.push_back(newInterval);
    while (i < intervals.size()) {
        result.push_back(intervals[i]);
        i++;
    }
    return result;
}

What is the bug in this code if any?

medium

A. No bug; the code correctly inserts and merges intervals

B. The first while loop condition should use <= instead of <

C. The second while loop should check intervals[i].second instead of intervals[i].first

D. The newInterval is not pushed back at the correct position

Solution

1. Step 1: Analyze the first while loop

   The first loop adds all intervals that end before the new interval starts, correctly skipping non-overlapping intervals before newInterval.

2. Step 2: Analyze the second while loop

   The second loop merges all intervals overlapping with newInterval by updating its start and end correctly.

3. Step 3: Analyze the final steps

   After merging, newInterval is added, then remaining intervals are appended. This maintains sorted order and merges properly.

4. Final Answer:

   No bug; the code correctly inserts and merges intervals -> Option A

5. Quick Check:

   Code logic matches insert and merge steps [OK]

Hint: Check loop conditions carefully for overlap and order [OK]

Common Mistakes:

• Changing loop conditions incorrectly
• Pushing newInterval too early or late
• Merging intervals incorrectly

5. You have a sorted list of intervals: [(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]. You want to insert a new interval (4, 8). What is the final list after insertion and merging?

hard

A. [(1, 2), (3, 5), (4, 8), (6, 7), (8, 10), (12, 16)]

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

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

D. [(1, 2), (3, 8), (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. The merged interval starts at min(3,4,6,8) = 3 and ends at max(5,7,8,10) = 10.

3. Step 3: Keep non-overlapping intervals

   Intervals (1, 2) and (12, 16) remain unchanged.

4. Final Answer:

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

5. Quick Check:

   Merge overlapping intervals = [(1, 2), (3, 10), (12, 16)] [OK]

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

Common Mistakes:

• Not merging all overlapping intervals
• Inserting new interval without merging
• Incorrect interval boundaries after merge