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 to keep the list neat and ordered.

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
Insert: [2,5]
Goal: merge overlapping intervals and keep order

Dry Run Walkthrough

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

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

Step 1: Add all intervals before [2,5] without overlap

[] -> null

Why: Intervals before new one that end before it starts are kept as is

Step 2: Merge [1,3] and [2,5] because they overlap

[1,5] -> null

Why: Overlap means we combine intervals into one covering both

Step 3: Check next interval [6,9], no overlap with [1,5], add it

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

Why: No overlap means we keep intervals separate and sorted

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

struct Interval {
    int start, end;
    Interval(int s, int e) : start(s), end(e) {}
};

vector<Interval> insertInterval(vector<Interval>& intervals, Interval newInterval) {
    vector<Interval> result;
    int i = 0, n = intervals.size();

    // Add all intervals ending before newInterval starts
    while (i < n && intervals[i].end < newInterval.start) {
        result.push_back(intervals[i]);
        i++;
    }

    // Merge overlapping intervals with newInterval
    while (i < n && intervals[i].start <= newInterval.end) {
        newInterval.start = min(newInterval.start, intervals[i].start);
        newInterval.end = max(newInterval.end, intervals[i].end);
        i++;
    }
    result.push_back(newInterval); // Add merged interval

    // Add remaining intervals
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

void printIntervals(const vector<Interval>& intervals) {
    for (const auto& interval : intervals) {
        cout << "[" << interval.start << "," << interval.end << "] -> ";
    }
    cout << "null" << endl;
}

int main() {
    vector<Interval> intervals = {Interval(1,3), Interval(6,9)};
    Interval newInterval(2,5);
    vector<Interval> result = insertInterval(intervals, newInterval);
    printIntervals(result);
    return 0;
}

while (i < n && intervals[i].end < newInterval.start) {

Add intervals that end before new interval starts

while (i < n && intervals[i].start <= newInterval.end) {

Merge intervals overlapping with new interval

newInterval.start = min(newInterval.start, intervals[i].start);

Update start of merged interval

newInterval.end = max(newInterval.end, intervals[i].end);

Update end of merged interval

result.push_back(newInterval);

Add merged interval to result

while (i < n) {

Add remaining intervals after merged one

Output

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

Complexity Analysis

Time: O(n) because we scan the list once to insert and merge intervals

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

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

Edge Cases

empty list

new interval is simply added as the only interval

DSA C++

while (i < n && intervals[i].end < newInterval.start) {

new interval before all intervals

new interval is added at the start without merges

DSA C++

while (i < n && intervals[i].end < newInterval.start) {

new interval after all intervals

new interval is added at the end without merges

DSA C++

while (i < n) {

new interval overlaps multiple intervals

all overlapping intervals are merged into one

DSA C++

while (i < n && intervals[i].start <= newInterval.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 ranges efficiently.

Common Mistakes

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

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

Summary

Inserts a new interval into a sorted list and merges overlapping intervals.

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

The key is to merge all overlapping intervals before inserting the new combined interval.

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