Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Removing the fewest intervals = keeping the most non-overlapping ones.
  2. 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