Merge Overlapping Intervals in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort intervals by their start time.

DSA C++

sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
    return a[[1]] < b[[2]];
});

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

A0

B1

C2

Da

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong index for sorting.

Comparing with 'a' or other variables instead of indices.

We sort intervals by their start time, which is at index 0 in each interval vector.

2fill in blank

medium

Complete the code to check if current interval overlaps with the last merged interval.

DSA C++

if (intervals[i][0] [1] merged.back()[1]) {
    merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
    merged.push_back(intervals[i]);
}

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

A>

B<=

C>=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '<=' misses touching intervals.

Using '>' or '>=' reverses the logic.

Intervals overlap if the current start is less than or equal to the last merged end.

3fill in blank

hard

Fix the error in updating the end of the last merged interval.

DSA C++

merged.back()[1] = [1](merged.back()[1], intervals[i][1]);

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

Amin

Bsum

Cabs

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Using min() shrinks the interval incorrectly.

Using abs() or sum() causes wrong results or errors.

We update the end to the maximum of the two ends to cover the full merged interval.

4fill in blank

hard

Fill both blanks to complete the loop that merges intervals.

DSA C++

for (int [1] = 1; [1] < intervals.size(); [2]++) {
    if (intervals[i][0] <= merged.back()[1]) {
        merged.back()[1] = max(merged.back()[1], intervals[i][1]);
    } else {
        merged.push_back(intervals[i]);
    }
}

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

Ai

Bj

Ck

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names in initialization and increment.

Using variables not declared or inconsistent.

The loop variable is 'i' used consistently for indexing intervals.

5fill in blank

hard

Fill all three blanks to create a map of interval starts to their lengths for intervals longer than 2.

DSA C++

map<int, int> intervalLengths = {
    {interval[[1]], interval[[2]] - interval[[3]]} 
    for (const auto& interval : intervals) if (interval[1] - interval[0] > 2)
};

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

A0

B1

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up start and end indices.

Using wrong indices for subtraction.

Start is at index 0, end at index 1, length is end - start.

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