Insert Interval into Sorted List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting interval into sorted list

What is the output of the following C++ code that inserts an interval into a sorted list of intervals?

DSA C++

std::vector<std::pair<int,int>> insertInterval(std::vector<std::pair<int,int>> intervals, std::pair<int,int> newInterval) {
    std::vector<std::pair<int,int>> 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;
}

#include <iostream>
int main() {
    std::vector<std::pair<int,int>> intervals = {{1,3}, {6,9}};
    std::pair<int,int> newInterval = {2,5};
    auto result = insertInterval(intervals, newInterval);
    for (auto &interval : result) {
        std::cout << "{" << interval.first << "," << interval.second << "} ";
    }
    return 0;
}

A {2,5} {6,9}

B {1,3} {2,5} {6,9}

C {1,5} {6,9}

D {1,3} {6,9} {2,5}

💡 Hint

Think about how overlapping intervals merge into one.

The new interval {2,5} overlaps with {1,3}, so they merge into {1,5}. The interval {6,9} remains separate.

❓ Predict Output

intermediate

Result after inserting non-overlapping interval

What is the output of this code after inserting a non-overlapping interval into a sorted list?

DSA C++

std::vector<std::pair<int,int>> insertInterval(std::vector<std::pair<int,int>> intervals, std::pair<int,int> newInterval) {
    std::vector<std::pair<int,int>> 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;
}

#include <iostream>
int main() {
    std::vector<std::pair<int,int>> intervals = {{1,2}, {3,5}, {6,7}, {8,10}, {12,16}};
    std::pair<int,int> newInterval = {17,19};
    auto result = insertInterval(intervals, newInterval);
    for (auto &interval : result) {
        std::cout << "{" << interval.first << "," << interval.second << "} ";
    }
    return 0;
}

A {1,2} {3,5} {6,7} {8,10} {12,16} {17,19}

B {1,2} {3,5} {6,7} {8,10} {12,16} {16,19}

C {1,2} {3,5} {6,7} {8,10} {12,16}

D {1,2} {3,5} {6,7} {8,10} {12,16} {17,18}

💡 Hint

New interval does not overlap, so it is added at the end.

Since {17,19} does not overlap with any existing intervals, it is simply appended at the end.

🔧 Debug

advanced

Identify the error in interval insertion code

What error will this code produce when inserting an interval into a sorted list?

DSA C++

std::vector<std::pair<int,int>> insertInterval(std::vector<std::pair<int,int>> intervals, std::pair<int,int> newInterval) {
    std::vector<std::pair<int,int>> 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;
}

#include <iostream>
int main() {
    std::vector<std::pair<int,int>> intervals = {{1,3}, {6,9}};
    std::pair<int,int> newInterval = {2,5};
    auto result = insertInterval(intervals, newInterval);
    for (auto &interval : result) {
        std::cout << "{" << interval.first << "," << interval.second << "} ";
    }
    return 0;
}

A Output: {1,5} {6,9}

B Output: {1,3} {2,5} {6,9}

C Output: {1,3} {6,9}

D Output: {1,5} {6,9} {2,5}

💡 Hint

Check the comparison operators in the while loops carefully.

The use of <= and < in the while loops causes the merging condition to be incorrect, so intervals are not merged properly.

🧠 Conceptual

advanced

Number of intervals after insertion and merge

Given a sorted list of intervals {{1,2}, {3,5}, {6,7}, {8,10}, {12,16}} and a new interval {4,8}, how many intervals will be in the list after inserting and merging?

A 5

B 4

C 6

D 3

💡 Hint

Consider which intervals overlap with the new interval.

The new interval {4,8} overlaps with {3,5}, {6,7}, and {8,10}, merging them into one interval {3,10}. The final list is {1,2}, {3,10}, {12,16}, so 3 intervals.

🚀 Application

expert

Final intervals after multiple insertions

Starting with an empty list, insert intervals in this order: {5,7}, {1,3}, {2,6}, {10,12}. What is the final list of intervals after all insertions and merges?

A {1,7} {10,12}

B {1,3} {2,6} {5,7} {10,12}

C {1,6} {5,7} {10,12}

D {1,7} {2,6} {10,12}

💡 Hint

Merge intervals as soon as they overlap after each insertion.

Inserting {5,7} then {1,3} results in {1,3}, {5,7}. Inserting {2,6} merges {1,3}, {2,6}, and {5,7} into {1,7}. Finally, {10,12} is separate. Final list: {1,7}, {10,12}.

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