Merge Overlapping Intervals in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merging Overlapping Intervals

What is the output of the following C++ code that merges overlapping intervals?

DSA C++

std::vector<std::pair<int,int>> intervals = {{1,3},{2,6},{8,10},{15,18}};

std::sort(intervals.begin(), intervals.end());

std::vector<std::pair<int,int>> merged;
for (auto interval : intervals) {
    if (merged.empty() || merged.back().second < interval.first) {
        merged.push_back(interval);
    } else {
        merged.back().second = std::max(merged.back().second, interval.second);
    }
}

for (auto interval : merged) {
    std::cout << "{" << interval.first << "," << interval.second << "} ";
}

A {1,6} {8,10} {15,18}

B {1,3} {2,6} {8,10} {15,18}

C {1,3} {8,10} {15,18}

D {1,6} {2,6} {8,10} {15,18}

💡 Hint

Look at how intervals are merged when they overlap.

The code sorts intervals and merges overlapping ones by extending the end of the last merged interval.

❓ Predict Output

intermediate

Result after merging intervals with nested overlaps

What is the output of this code merging intervals with nested overlaps?

DSA C++

std::vector<std::pair<int,int>> intervals = {{1,4},{4,5},{5,6},{7,8}};

std::sort(intervals.begin(), intervals.end());

std::vector<std::pair<int,int>> merged;
for (auto interval : intervals) {
    if (merged.empty() || merged.back().second < interval.first) {
        merged.push_back(interval);
    } else {
        merged.back().second = std::max(merged.back().second, interval.second);
    }
}

for (auto interval : merged) {
    std::cout << "{" << interval.first << "," << interval.second << "} ";
}

A {1,4} {4,5} {5,6} {7,8}

B {1,5} {5,6} {7,8}

C {1,6} {7,8}

D {1,4} {5,6} {7,8}

💡 Hint

Check how intervals that touch at edges merge.

Intervals {1,4}, {4,5}, and {5,6} merge into {1,6} because they overlap or touch.

🔧 Debug

advanced

Identify the error in this merge intervals code

What error does this code produce when merging intervals?

DSA C++

std::vector<std::pair<int,int>> intervals = {{1,3},{3,4},{5,7}};

std::vector<std::pair<int,int>> merged;
for (auto interval : intervals) {
    if (merged.empty() || merged.back().second <= interval.first) {
        merged.push_back(interval);
    } else {
        merged.back().second = std::max(merged.back().second, interval.second);
    }
}

for (auto interval : merged) {
    std::cout << "{" << interval.first << "," << interval.second << "} ";
}

A {1,3} {3,4} {5,7}

B {1,3} {5,7}

C {1,4} {5,7}

D {1,4} {2,4} {5,7}

💡 Hint

Check the condition that decides when to merge.

The condition uses <= which causes intervals that touch to not merge, so {1,3} and {3,4} remain separate.

❓ Predict Output

advanced

Output of merging intervals with unsorted input

What is the output after merging these unsorted intervals?

DSA C++

std::vector<std::pair<int,int>> intervals = {{5,7},{1,4},{2,6},{8,10}};

std::sort(intervals.begin(), intervals.end());

std::vector<std::pair<int,int>> merged;
for (auto interval : intervals) {
    if (merged.empty() || merged.back().second < interval.first) {
        merged.push_back(interval);
    } else {
        merged.back().second = std::max(merged.back().second, interval.second);
    }
}

for (auto interval : merged) {
    std::cout << "{" << interval.first << "," << interval.second << "} ";
}

A {1,4} {2,6} {5,7} {8,10}

B {1,7} {8,10}

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

D {5,7} {1,4} {2,6} {8,10}

💡 Hint

Remember the code sorts intervals before merging.

After sorting, intervals merge into {1,7} and {8,10}.

🧠 Conceptual

expert

Minimum number of intervals after merging

Given intervals {{1,5},{2,3},{4,6},{7,8},{8,10},{12,15}}, what is the minimum number of intervals after merging all overlapping ones?

A 5

B 2

C 4

D 3

💡 Hint

Merge intervals that overlap or touch.

Intervals {1,5}, {2,3}, and {4,6} merge into one {1,6}. Intervals {7,8} and {8,10} merge into {7,10}. Interval {12,15} stays separate. Total 3 intervals.

Practice

1. What is the main purpose of the Merge Overlapping Intervals algorithm?

easy

A. To find the maximum interval length

B. To combine all intervals that overlap into a single continuous interval

C. To sort intervals in descending order

D. To remove all intervals that overlap

Solution

1. Step 1: Understand the problem goal

   The algorithm aims to merge intervals that share common parts so they become one continuous interval.

2. Step 2: Clarify what merging means

   Merging means combining overlapping intervals into one that covers the entire range of those intervals.

3. Final Answer:

   To combine all intervals that overlap into a single continuous interval -> Option B

4. Quick Check:

   Merge overlapping intervals = combine overlaps [OK]

Hint: Think of joining overlapping time slots into one [OK]

Common Mistakes:

• Confusing merging with sorting
• Thinking it removes intervals instead of combining
• Assuming it finds max length only

2. Which of the following C++ code snippets correctly sorts a vector of intervals by their start time before merging?

easy

A. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; });

B. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[1] > b[1]; });

C. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[1] < b[1]; });

D. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] > b[0]; });

Solution

1. Step 1: Identify sorting by start time

   We need to sort intervals by their first element (start time) in ascending order.

2. Step 2: Check lambda comparator correctness

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; }); uses a lambda that compares a[0] < b[0], which sorts ascending by start time correctly.

3. Final Answer:

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; }); -> Option A

4. Quick Check:

   Sort by start ascending = a[0] < b[0] [OK]

Hint: Sort intervals by start ascending using a lambda [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Sorting in descending order
• Using default sort without comparator on vector of vectors

3. What is the output of the following C++ code that merges overlapping intervals?

std::vector intervals = {{1,3},{2,6},{8,10},{15,18}};
// After merging overlapping intervals
// Print merged intervals
for (auto &interval : merged) {
    std::cout << "[" << interval[0] << "," << interval[1] << "] ";
}

medium

A. [1,6] [8,10] [15,18]

B. [1,3] [2,6] [8,10] [15,18]

C. [1,6] [2,6] [8,10] [15,18]

D. [1,3] [8,10] [15,18]

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [1,3], [2,6], [8,10], [15,18]

2. Step 2: Merge overlapping intervals

   [1,3] and [2,6] overlap, merge to [1,6]. Others remain separate.

3. Final Answer:

   [1,6] [8,10] [15,18] -> Option A

4. Quick Check:

   Merged intervals = [1,6], [8,10], [15,18] [OK]

Hint: Merge intervals by expanding end if overlap found [OK]

Common Mistakes:

• Not merging overlapping intervals
• Printing original intervals without merge
• Merging incorrectly leaving duplicates

4. Identify the bug in this C++ code snippet for merging intervals:

std::vector mergeIntervals(std::vector &intervals) {
    std::vector merged;
    for (auto &interval : intervals) {
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = std::max(merged.back()[1], interval[1]);
        }
    }
    return merged;
}

medium

A. Pushing intervals without checking overlap

B. Using std::max incorrectly

C. Intervals are not sorted before merging

D. Returning merged by reference instead of value

Solution

1. Step 1: Check preconditions for merging

   Merging requires intervals sorted by start time to work correctly.

2. Step 2: Identify missing sorting step

   The code does not sort intervals before merging, so overlapping intervals may be missed.

3. Final Answer:

   Intervals are not sorted before merging -> Option C

4. Quick Check:

   Sort intervals first to merge correctly [OK]

Hint: Always sort intervals by start before merging [OK]

Common Mistakes:

• Skipping sorting step
• Assuming input is sorted
• Misusing std::max function

5. Given intervals [[1,4],[4,5],[7,9],[8,10]], what is the merged output after applying the merge overlapping intervals algorithm?

hard

A. [[1,10]]

B. [[1,4],[4,5],[7,9],[8,10]]

C. [[1,4],[5,7],[8,10]]

D. [[1,5],[7,10]]

Solution

1. Step 1: Sort intervals by start time

   Intervals are already sorted: [1,4], [4,5], [7,9], [8,10]

2. Step 2: Merge overlapping or touching intervals

   [1,4] and [4,5] touch at 4, merge to [1,5]. [7,9] and [8,10] overlap, merge to [7,10].

3. Final Answer:

   [[1,5],[7,10]] -> Option D

4. Quick Check:

   Touching intervals merge too [OK]

Hint: Merge intervals that overlap or touch at boundaries [OK]

Common Mistakes:

• Not merging intervals that touch at endpoints
• Leaving intervals separate when they overlap
• Merging all intervals incorrectly into one