Non Overlapping Intervals Minimum Removal in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

What is the output of the following C++ code that calculates the minimum number of intervals to remove to avoid overlaps?

DSA C++

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

int eraseOverlapIntervals(vector<pair<int,int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b){ return a.second < b.second; });
    int count = 0;
    int end = intervals[0].second;
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i].first < end) {
            count++;
        } else {
            end = intervals[i].second;
        }
    }
    return count;
}

int main() {
    vector<pair<int,int>> intervals = {{1,3},{2,4},{3,5},{6,7}};
    cout << eraseOverlapIntervals(intervals) << endl;
    return 0;
}

A 1

B 3

C 2

D 0

💡 Hint

Sort intervals by their end time and count overlaps.

The code sorts intervals by their end time and counts how many intervals overlap with the previous chosen interval. Only one interval needs to be removed to avoid overlaps.

🧠 Conceptual

intermediate

Understanding the greedy choice in interval removal

Why does sorting intervals by their end time help in minimizing the number of intervals to remove?

A Because sorting by end time groups overlapping intervals together.

B Because choosing intervals with earliest end time leaves more room for following intervals.

C Because sorting by length of intervals guarantees minimal removals.

D Because sorting by start time always leads to minimum removals.

💡 Hint

Think about how choosing intervals affects the space left for others.

Choosing intervals that end earliest allows more intervals to fit after them without overlap, minimizing removals.

🔧 Debug

advanced

Identify the error in interval removal code

What error does the following code produce when run with intervals {{1,4},{2,3},{3,5},{6,7}}? int eraseOverlapIntervals(vector>& intervals) { sort(intervals.begin(), intervals.end()); int count = 0; int end = intervals[0].second; for(int i = 1; i < intervals.size(); i++) { if(intervals[i].first < end) { count++; } else { end = intervals[i].second; } } return count; }

A Logic error: returns 2 instead of 1

B Compilation error due to missing comparator

C Runtime error: out_of_range exception

D No error, returns 1

💡 Hint

Check how intervals are sorted and how end is updated.

Sorting by default sorts by start time, not end time, so the greedy choice fails and count is incorrect.

❓ Predict Output

advanced

Output of minimum removals with nested intervals

What is the output of this code for intervals {{1,10},{2,3},{3,4},{4,5}}?

DSA C++

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

int eraseOverlapIntervals(vector<pair<int,int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b){ return a.second < b.second; });
    int count = 0;
    int end = intervals[0].second;
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i].first < end) {
            count++;
        } else {
            end = intervals[i].second;
        }
    }
    return count;
}

int main() {
    vector<pair<int,int>> intervals = {{1,10},{2,3},{3,4},{4,5}};
    cout << eraseOverlapIntervals(intervals) << endl;
    return 0;
}

A 2

B 3

C 0

D 1

💡 Hint

The large interval overlaps with all smaller ones.

The large interval {1,10} overlaps with all others, so it must be removed to avoid overlaps, resulting in 1 removal.

🚀 Application

expert

Minimum removals for intervals with same end time

Given intervals {{1,5},{2,5},{3,5},{4,5}}, what is the minimum number of intervals to remove to avoid overlaps?

A 0

B 1

C 3

D 4

💡 Hint

All intervals end at the same time, so only one can remain.

Since all intervals end at 5 and start at different times, they all overlap. Only one can stay, so 3 must be removed.

Practice

1. What is the main goal of the Non Overlapping Intervals Minimum Removal problem?

easy

A. To merge all intervals into one

B. To find the maximum number of overlapping intervals

C. To remove the minimum number of intervals so that the remaining intervals do not overlap

D. To sort intervals by their start time

Solution

1. Step 1: Understand the problem goal

   The problem asks to remove as few intervals as possible so that no two intervals overlap.

2. Step 2: Clarify what non-overlapping means

   Non-overlapping means for any two intervals, one ends before the other starts.

3. Final Answer:

   To remove the minimum number of intervals so that the remaining intervals do not overlap -> Option C

4. Quick Check:

   Minimum removal = non-overlapping intervals [OK]

Hint: Focus on removing intervals, not merging or counting overlaps [OK]

Common Mistakes:

• Confusing removal with merging intervals
• Thinking the goal is to count overlaps
• Sorting intervals without removing

2. Which of the following C++ code snippets correctly sorts intervals by their end time for the minimum removal problem?

easy

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

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

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

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

Solution

1. Step 1: Identify sorting criteria for minimum removal

   We sort intervals by their end time ascending to greedily pick intervals that finish earliest.

2. Step 2: Check code correctness

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.end < b.end; }); uses a lambda comparing a.end < b.end, which is correct for sorting by end time ascending.

3. Final Answer:

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

4. Quick Check:

   Sort by end time ascending = std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.end < b.end; }); [OK]

Hint: Sort intervals by end time ascending for greedy approach [OK]

Common Mistakes:

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

3. What is the output of the following C++ code snippet?

struct Interval { int start, end; };
std::vector<Interval> intervals = {{1,3}, {2,4}, {3,5}};
std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.end < b.end; });
int count = 0, end_time = INT_MIN;
for (auto &interval : intervals) {
  if (interval.start >= end_time) {
    end_time = interval.end;
  } else {
    count++;
  }
}
std::cout << count << std::endl;

medium

A. 2

B. 1

C. 0

D. 3

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals by end: (1,3), (2,4), (3,5)

2. Step 2: Iterate and count removals

   Start with end_time = -∞ - Interval (1,3): start 1 >= -∞, keep, end_time=3 - Interval (2,4): start 2 < 3, overlap, count=1 - Interval (3,5): start 3 >= 3, keep, end_time=5

3. Final Answer:

   1 -> Option B

4. Quick Check:

   One overlap removed = 1 [OK]

Hint: Count overlaps by comparing start with last end time [OK]

Common Mistakes:

• Not updating end_time correctly
• Counting non-overlapping intervals as removals
• Sorting incorrectly before iteration

4. Identify the bug in the following C++ code for minimum interval removal:

std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.start < b.start; });
int count = 0, end_time = INT_MIN;
for (auto &interval : intervals) {
  if (interval.start >= end_time) {
    end_time = interval.end;
  } else {
    count++;
  }
}
return count;

medium

A. Not initializing count to 1 causes off-by-one error

B. Using INT_MIN for end_time causes overflow

C. Missing check for empty intervals vector

D. Sorting by start time instead of end time causes incorrect removal count

Solution

1. Step 1: Check sorting criteria

   The code sorts intervals by start time, but greedy approach requires sorting by end time to minimize removals.

2. Step 2: Understand impact on counting

   Sorting by start time can cause counting more removals than needed because intervals ending earlier are not prioritized.

3. Final Answer:

   Sorting by start time instead of end time causes incorrect removal count -> Option D

4. Quick Check:

   Sort by end time, not start time [OK]

Hint: Always sort by end time for minimum removal [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Assuming INT_MIN causes overflow here
• Ignoring empty input checks

5. Given intervals [[1,2],[2,3],[3,4],[1,3]], what is the minimum number of intervals to remove to make the rest non-overlapping?

hard

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: [1,2], [2,3], [1,3], [3,4]

2. Step 2: Select intervals greedily and count removals

   Keep [1,2] (end=2) - [2,3]: start 2 >= 2, keep - [1,3]: start 1 < 2 (overlaps with [1,2]), remove (count=1) - [3,4]: start 3 >= 3, keep Total removals so far: 1 But [1,3] overlaps with [1,2], removing it once is enough. Check if any other removals needed: none Total removals = 1

3. Step 3: Re-examine intervals order

   Actually, sorting by end time ascending is: [1,2], [2,3], [1,3], [3,4] But [1,3] overlaps with [1,2], so removing it once suffices. If we keep [1,2], [2,3], [3,4], we remove [1,3] only once. So minimum removals = 1

4. Final Answer:

   1 -> Option A

5. Quick Check:

   Remove overlapping [1,3] only once [OK]

Hint: Sort by end time, greedily pick intervals, count removals [OK]

Common Mistakes:

• Removing too many intervals unnecessarily
• Not sorting by end time
• Confusing overlapping intervals