Practice › Greedy
Non-overlapping Intervals
Medium · Greedy · Asked at Amazon, Google, Meta, Microsoft
Print the minimum number of intervals to remove so that the remaining intervals do not overlap. Intervals that only touch at an endpoint (like [1,2] and [2,3]) do not overlap.
Input
First line: n. Next n lines: start end.
Output
The minimum number of removals.
Constraints
- 1 ≤ n ≤ 10^5
- -5 · 10^4 ≤ start < end ≤ 5 · 10^4
Keep as many intervals as possible: sort by end and greedily keep each interval that starts at or after the end of the last kept one (activity selection).
Example 1
Input
4 1 2 2 3 3 4 1 3
Output
1
Example 2
Input
3 1 2 1 2 1 2
Output
2
Hints
- Removing the fewest intervals = keeping the most non-overlapping ones.
- Sort by end time and keep an interval whenever it starts at or after the end of the last kept one (activity selection).
Approach
Choosing the interval that ends earliest leaves the most room for the rest — the classic exchange argument. After sorting by end, scan and keep interval [a, b] if a ≥ lastEnd (touching is allowed), updating lastEnd = b. The answer is n − kept.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<long long, long long>> iv(n); // (end, start)
for (auto &x : iv) cin >> x.second >> x.first;
sort(iv.begin(), iv.end());
long long lastEnd = LLONG_MIN;
int kept = 0;
for (auto &x : iv)
if (x.second >= lastEnd) kept++, lastEnd = x.first;
cout << n - kept << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
iv = sorted(((data[2 + 2 * i], data[1 + 2 * i]) for i in range(n))) # (end, start)
last, kept = float("-inf"), 0
for b, a in iv:
if a >= last:
kept += 1
last = b
print(n - kept)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[][] iv = new long[n][2];
for (int i = 0; i < n; i++) {
iv[i][0] = sc.nextLong();
iv[i][1] = sc.nextLong();
}
Arrays.sort(iv, (a, b) -> Long.compare(a[1], b[1]));
long lastEnd = Long.MIN_VALUE;
int kept = 0;
for (long[] x : iv)
if (x[0] >= lastEnd) {
kept++;
lastEnd = x[1];
}
System.out.println(n - kept);
}
}Solve Non-overlapping Intervals online · All practice problems