LeetCode 1288 - Remove Covered Intervals

The problem gives us a list of intervals, where each interval is represented as [li, ri], corresponding to the half open

leetcodemediumarraysorting

LeetCode Problem 1288

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

Problem Understanding

The problem gives us a list of intervals, where each interval is represented as [li, ri], corresponding to the half open interval [li, ri). We need to remove every interval that is completely covered by another interval in the list.

An interval [a, b) is considered covered by [c, d) if:

  • c <= a
  • b <= d

This means the entire interval [a, b) lies inside [c, d).

The task is not to return the remaining intervals themselves. Instead, we only need to return how many intervals remain after removing all covered intervals.

For example, if we have:

[[1,4],[3,6],[2,8]]

The interval [3,6] is fully contained inside [2,8], because:

  • 2 <= 3
  • 6 <= 8

So [3,6] is removed, leaving two intervals.

The constraints are relatively small:

  • Up to 1000 intervals
  • Interval endpoints up to 100000

Because the input size is moderate, even an O(n^2) solution would technically pass. However, the problem is designed to reward a more elegant sorting-based approach.

Several edge cases are important to consider:

  • Intervals with the same starting point
  • Intervals nested deeply inside another interval
  • Intervals that overlap but are not covered
  • A single interval input
  • Intervals already sorted or completely unsorted

The problem also guarantees that all intervals are unique, which removes ambiguity around duplicate intervals.

Approaches

Brute Force Approach

The most direct solution is to compare every interval with every other interval.

For each interval i, we check whether there exists another interval j such that:

j.start <= i.start
j.end >= i.end

If such an interval exists, then interval i is covered and should not be counted.

This approach is correct because it explicitly tests the definition of coverage for every pair of intervals. However, it requires checking all pairs, resulting in quadratic time complexity.

With n intervals, we perform up to n * n comparisons, giving a time complexity of O(n^2).

Optimal Approach

The key insight is that sorting the intervals allows us to detect covered intervals in a single pass.

We sort intervals using two rules:

  1. Sort by starting point in ascending order
  2. If two intervals have the same start, sort by ending point in descending order

The second rule is extremely important.

Consider:

[1,4], [1,6]

If we sorted ends in ascending order, [1,4] would appear first, making it harder to recognize that it is covered by [1,6].

By sorting ends in descending order, larger intervals come first:

[1,6], [1,4]

Now we only need to track the largest ending point seen so far.

As we scan through the sorted intervals:

  • If the current interval's end is less than or equal to the maximum end seen so far, it is covered
  • Otherwise, it is not covered, and we update the maximum end

This reduces the problem to a single linear scan after sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare every interval against every other interval
Optimal O(n log n) O(1) or O(log n) Sort intervals, then scan once to count uncovered intervals

Algorithm Walkthrough

  1. Sort the intervals by starting point in ascending order.

This ensures intervals are processed from left to right. 2. When two intervals have the same starting point, sort by ending point in descending order.

This guarantees that larger intervals appear before smaller contained intervals. Without this rule, covered intervals with equal starts could be missed. 3. Initialize two variables:

  • remaining_intervals, initially 0
  • max_end, initially 0

max_end tracks the farthest ending point encountered so far. 4. Iterate through the sorted intervals one by one. 5. For each interval [start, end]:

  • If end <= max_end, then this interval is covered by a previously processed interval.

  • Otherwise, the interval is not covered:

  • Increment remaining_intervals

  • Update max_end = end

  1. After processing all intervals, return remaining_intervals.

Why it works

After sorting, every previously processed interval has a start point less than or equal to the current interval's start point.

Because intervals with equal starts are sorted by decreasing end, any interval capable of covering the current interval must appear earlier in the traversal.

Therefore, if the current interval's end is less than or equal to the maximum end seen so far, some earlier interval completely covers it.

This invariant guarantees correctness throughout the scan.

Python Solution

from typing import List

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda interval: (interval[0], -interval[1]))

        remaining_intervals = 0
        max_end = 0

        for start, end in intervals:
            if end > max_end:
                remaining_intervals += 1
                max_end = end

        return remaining_intervals

The implementation begins by sorting the intervals according to the required ordering. The lambda key sorts first by starting position ascending, then by ending position descending.

The variable max_end stores the farthest right endpoint encountered so far. During traversal, if the current interval ends after max_end, it cannot be covered by any previous interval, so we count it and update max_end.

If the current interval ends at or before max_end, then a previously processed interval already fully contains it, so it is skipped.

The entire algorithm after sorting is a single linear scan.

Go Solution

package main

import "sort"

func removeCoveredIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] > intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})

	remainingIntervals := 0
	maxEnd := 0

	for _, interval := range intervals {
		end := interval[1]

		if end > maxEnd {
			remainingIntervals++
			maxEnd = end
		}
	}

	return remainingIntervals
}

The Go implementation follows the same logic as the Python version.

The main difference is the use of sort.Slice to provide a custom comparator for sorting intervals.

Go slices are reference-like structures, so sorting modifies the original slice directly. Since interval endpoints are constrained to at most 100000, integer overflow is not a concern.

The algorithm uses only a few integer variables, so memory usage remains minimal.

Worked Examples

Example 1

Input:

[[1,4],[3,6],[2,8]]

After sorting:

[[1,4],[2,8],[3,6]]
Current Interval max_end Before Covered? remaining_intervals max_end After
[1,4] 0 No 1 4
[2,8] 4 No 2 8
[3,6] 8 Yes 2 8

Final answer:

2

Example 2

Input:

[[1,4],[2,3]]

After sorting:

[[1,4],[2,3]]
Current Interval max_end Before Covered? remaining_intervals max_end After
[1,4] 0 No 1 4
[2,3] 4 Yes 1 4

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Only a few variables are used, aside from sorting overhead

The scan itself is linear, requiring O(n) time. However, sorting requires O(n log n) time, which becomes the dominant factor.

The algorithm uses constant extra variables. Depending on the language implementation of sorting, recursion stack usage may contribute O(log n) auxiliary space.

Test Cases

from typing import List

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda interval: (interval[0], -interval[1]))

        remaining_intervals = 0
        max_end = 0

        for start, end in intervals:
            if end > max_end:
                remaining_intervals += 1
                max_end = end

        return remaining_intervals

solution = Solution()

assert solution.removeCoveredIntervals([[1,4],[3,6],[2,8]]) == 2  # basic example
assert solution.removeCoveredIntervals([[1,4],[2,3]]) == 1  # one interval covered
assert solution.removeCoveredIntervals([[1,2]]) == 1  # single interval
assert solution.removeCoveredIntervals([[1,10],[2,9],[3,8],[4,7]]) == 1  # deeply nested intervals
assert solution.removeCoveredIntervals([[1,2],[2,3],[3,4]]) == 3  # overlapping but not covered
assert solution.removeCoveredIntervals([[1,4],[1,5]]) == 1  # same start, larger interval covers smaller
assert solution.removeCoveredIntervals([[1,5],[1,4],[1,3]]) == 1  # multiple equal starts
assert solution.removeCoveredIntervals([[0,10],[5,12]]) == 2  # overlap without coverage
assert solution.removeCoveredIntervals([[1,100000],[2,99999]]) == 1  # large endpoint values
assert solution.removeCoveredIntervals([[3,10],[4,10],[5,11]]) == 2  # equal ends with different starts
Test Why
[[1,4],[3,6],[2,8]] Validates the main example
[[1,4],[2,3]] Tests direct coverage
[[1,2]] Tests smallest possible input
[[1,10],[2,9],[3,8],[4,7]] Tests multiple nested intervals
[[1,2],[2,3],[3,4]] Ensures overlap is not confused with coverage
[[1,4],[1,5]] Tests identical starts
[[1,5],[1,4],[1,3]] Verifies descending-end sorting behavior
[[0,10],[5,12]] Tests partial overlap without coverage
[[1,100000],[2,99999]] Tests large values
[[3,10],[4,10],[5,11]] Tests intervals sharing the same end

Edge Cases

One important edge case occurs when multiple intervals share the same starting point. For example:

[[1,5],[1,4]]

A naive sorting strategy that sorts ending points ascending could process [1,4] first, making it difficult to recognize that it is covered. Sorting ending points in descending order ensures the larger interval appears first, allowing the algorithm to detect coverage correctly.

Another important case is overlapping intervals that are not covered:

[[1,4],[3,6]]

These intervals overlap, but neither fully contains the other. A buggy implementation might incorrectly remove one interval simply because overlap exists. The algorithm avoids this mistake by checking only whether end <= max_end.

Deeply nested intervals are another common source of bugs:

[[1,10],[2,9],[3,8],[4,7]]

Every interval except the first is covered. The algorithm handles this efficiently because max_end remains 10 throughout the scan, causing every later interval to be recognized as covered immediately.

A final edge case involves the smallest possible input:

[[1,2]]

Since no other interval exists to cover it, the answer must be 1. The algorithm naturally handles this because the first interval always increases max_end and is counted.