Non Overlapping Intervals Minimum Removal in DSA C++

Mental Model

We want to remove the fewest intervals so that no intervals overlap. We do this by always keeping the interval that ends earliest to leave room for others.

Analogy: Imagine scheduling meetings in one room. To fit the most meetings without overlap, you pick the meeting that finishes earliest first, then pick the next meeting that starts after it ends, and so on. The meetings you can't fit must be removed.

Intervals: [1,3] -> [2,4] -> [3,5] -> [6,7]
Goal: Remove minimum intervals so none overlap
Initial:
[1,3] -> [2,4] -> [3,5] -> [6,7]
After removal:
[1,3] -> [3,5] -> [6,7]

Dry Run Walkthrough

Input: intervals: [[1,3], [2,4], [3,5], [6,7]]

Goal: Remove the minimum number of intervals so that the remaining intervals do not overlap

Step 1: Sort intervals by their end time

[1,3] -> [2,4] -> [3,5] -> [6,7]

Why: Sorting by end time helps us pick intervals that finish earliest to maximize room for others

Step 2: Select first interval [1,3], set end = 3

[1,3] ↑ -> [2,4] -> [3,5] -> [6,7]

Why: We keep the first interval and track its end to compare with next intervals

Step 3: Check [2,4]: start 2 < end 3, so it overlaps; remove it

[1,3] ↑ -> [2,4](removed) -> [3,5] -> [6,7]

Why: This interval overlaps with the last kept interval, so we remove it to avoid overlap

Step 4: Check [3,5]: start 3 >= end 3, keep it and update end = 5

[1,3] -> [3,5] ↑ -> [6,7]

Why: No overlap, so we keep this interval and update the end pointer

Step 5: Check [6,7]: start 6 >= end 5, keep it and update end = 7

[1,3] -> [3,5] -> [6,7] ↑

Why: No overlap, keep this interval as well

Result:

[1,3] -> [3,5] -> [6,7]
Minimum intervals removed: 1

Annotated Code

DSA C++

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

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        // Sort intervals by end time
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < end) {
                // Overlap found, remove this interval
                count++;
            } else {
                // No overlap, update end
                end = intervals[i][1];
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> intervals = {{1,3}, {2,4}, {3,5}, {6,7}};
    int result = sol.eraseOverlapIntervals(intervals);
    cout << "Minimum intervals removed: " << result << endl;
    return 0;
}

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

Sort intervals by their end time to prioritize earliest finishing intervals

int end = intervals[0][1];

Initialize end to the end time of the first interval kept

if (intervals[i][0] < end) { count++; } else { end = intervals[i][1]; }

If current interval starts before end, it overlaps and must be removed; else update end

Output

Minimum intervals removed: 1

Complexity Analysis

Time: O(n log n) because we sort the intervals and then scan them once

Space: O(1) because sorting is done in place and only a few variables are used

vs Alternative: A naive approach checking all pairs for overlap would be O(n^2), so sorting and greedy scanning is more efficient

Edge Cases

empty intervals list

returns 0 since no intervals to remove

DSA C++

if (intervals.empty()) return 0;

all intervals non-overlapping

returns 0 since no removals needed

DSA C++

if (intervals[i][0] < end) { count++; } else { end = intervals[i][1]; }

all intervals overlapping

removes all but one interval

DSA C++

if (intervals[i][0] < end) { count++; }

When to Use This Pattern

When you need to remove minimum intervals to avoid overlap, look for a greedy approach sorting by end time to keep intervals that finish earliest.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to correctly apply the greedy strategy

Mistake: Updating end pointer incorrectly when removing intervals
Fix: Only update end when you keep an interval, not when you remove it

Summary

Removes the minimum number of intervals so that no intervals overlap.

Use when you want to maximize the number of non-overlapping intervals by removing the fewest.

Always sort intervals by their end time and greedily keep intervals that finish earliest.

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