Remove Covered Intervals

Problem

An interval [a,b] is covered by [c,d] iff c ≤ a and b ≤ d. Return how many intervals remain after removing every covered one.

Constraints

• 1 ≤ n ≤ 1000

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

class Solution:
    def removeCoveredIntervals(self, intervals):
        intervals.sort(key=lambda x: (x[0], -x[1]))
        count = 0
        prev_end = 0
        for s, e in intervals:
            if e > prev_end:
                count += 1
                prev_end = e
        return count

Java

import java.util.*;
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int count = 0, end = 0;
        for (int[] x : intervals) {
            if (x[1] > end) { count++; end = x[1]; }
        }
        return count;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.