AlgoMaster Logo

Remove Covered Intervals

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We are given a list of intervals, and we need to remove any interval that is completely "inside" another interval. An interval [a, b) is covered by [c, d) when c <= a and b <= d. In other words, the covering interval starts at or before the smaller one and ends at or after it.

The question asks us to count how many intervals survive after removing all covered ones. An interval can be covered by any other interval in the list, not just an adjacent one. If two intervals are identical, one covers the other (and vice versa), so only one should remain. The constraints say all intervals are unique, so we do not have to handle exact duplicates here, but two intervals can still share a start or an end point.

Sorting the intervals in the right order reduces this to a single pass. If we sort by start point ascending and break ties by end point descending, then for any interval we examine, every interval that could cover it has already been seen. We only need to check whether its end point falls within the reach of the intervals before it.

Key Constraints:

  • 1 <= intervals.length <= 1000 → With n up to 1,000, an O(n^2) brute force runs in about 1,000,000 operations, which is feasible. An O(n log n) sorting approach is the better target.
  • 0 <= l_i < r_i <= 10^5 → Intervals are valid (start strictly less than end), so we do not need to handle empty or reversed intervals. Endpoints fit comfortably in a 32-bit integer, so there is no overflow risk in any language.
  • All intervals are unique → No exact duplicates, but two intervals can share the same start or end point.

Approach 1: Brute Force

Intuition

For each interval, check whether any other interval in the list covers it. An interval [a, b) is covered by [c, d) if c <= a and b <= d. If we find such a covering interval, we mark the current one as covered and do not count it.

This is O(n^2) because for each of the n intervals, we compare it against up to n - 1 others. With n up to 1,000, that is about a million comparisons, which runs well within typical limits.

Algorithm

  1. Initialize a counter count = 0.
  2. For each interval i, check all other intervals j:
    • If interval j covers interval i (meaning j.start <= i.start and i.end <= j.end), mark i as covered and break.
    • If i and j are identical, treat only the one with the smaller index as the coverer. Otherwise two equal intervals would each cover the other and both would be removed, leaving zero when one should survive.
  3. If interval i is not covered by any other interval, increment count.
  4. Return count.

Visualization and Code

Loading animation...

The brute force repeats comparisons because the intervals have no ordering to exploit. Sorting them so that every potential coverer appears before the intervals it might cover reduces the work to a single pass.

Approach 2: Sort and Greedy (Optimal)

Intuition

If we sort intervals by start point ascending, then any interval that could cover another must start at the same position or earlier. Ties on the start point need care. If two intervals share the same start, the longer one (larger end) should come first, so the shorter one appears after it and reads as covered.

The sorting rule is therefore: sort by start ascending, and break ties by end descending. After sorting, we track the maximum end point seen so far. If the current interval's end is within that maximum, it is covered. Otherwise it survives, and we update the maximum.

Algorithm

  1. Sort intervals by start ascending. If two intervals have the same start, sort by end descending.
  2. Initialize maxEnd = 0 and count = 0.
  3. For each interval [start, end] in the sorted list:
    • If end > maxEnd, this interval is not covered. Increment count and update maxEnd = end.
    • Otherwise (end <= maxEnd), this interval is covered. Skip it.
  4. Return count.

Visualization and Code

Loading animation...