LeetCode · #1288

Remove Covered Intervals Solution

Return the number of intervals that are NOT covered by another interval.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1288

🏗️

Pattern

Intervals — sort + track max end

Interval [a,b] is covered by [c,d] if c ≤ a and b ≤ d. Remove all covered intervals and return the count of remaining ones.

Example

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2 // [1,4] is covered by [2,8]? No — 2 > 1. [3,6] is covered by [2,8]? Yes — 2 ≤ 3 and 6 ≤ 8. // Remaining: [1,4] and [2,8]. Count = 2.

Constraints

• 1 ≤ intervals.length ≤ 1000 • intervals[i].length == 2 • 0 ≤ startᵢ < endᵢ ≤ 10⁵

Section Two · Approach 1

Brute Force — O(n²)

For each interval, check if any other interval covers it.

Problem: O(n²). Sort by start ascending, end descending. Then a single pass tracking max end — if current end ≤ maxEnd, it's covered.

Java — O(n²)

 class Solution {
public int removeCoveredIntervals(int[][] intervals) {
int n = intervals.length, removed = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j && intervals[j][0] <= intervals[i][0]
                         && intervals[i][1] <= intervals[j][1]) {
                    removed++; break;
                }
return n - removed;
    }
}

Python — O(n²)

 class Solution:
def removeCoveredIntervals(self, intervals: list[list[int]]) -> int:
        n = len(intervals)
        removed = 0 for i in range(n):
if any(j != i and intervals[j][0] <= intervals[i][0]
and intervals[i][1] <= intervals[j][1] for j in range(n)):
                removed += 1 return n - removed

Section Three · Approach 2

Sort + Track Max End — O(n log n)

Sort by start ascending. For same start, sort by end descending (longer intervals first). Track maxEnd. If current end ≤ maxEnd → covered. Else → not covered, update maxEnd.

💡 Mental model: Sort intervals by "who starts earliest, and among ties, who stretches farthest." Walk through: maintain the longest reach seen so far (maxEnd). If the current interval ends within that reach, it's completely inside an earlier one — remove it. Otherwise, it extends the reach — keep it.

Algorithm

Sort by start ascending, end descending (on ties).
count = 0, maxEnd = 0.
For each interval: if end > maxEnd → not covered, count++, maxEnd = end.
Return count.

Why sort end descending on start ties? If [1,10] and [1,4] have the same start, [1,4] is covered by [1,10]. By processing [1,10] first (larger end), maxEnd=10, and [1,4] has end=4 ≤ 10 → correctly identified as covered.

Section Four · Trace

Visual Walkthrough

Trace for intervals=[[1,4],[3,6],[2,8]].

Remove Covered Intervals — Sort + Max End

Section Five · Implementation

Code — Java & Python

Java — Sort + max end

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

Python — Sort + max end

 class Solution:
def removeCoveredIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        count = max_end = 0 for _, end in intervals:
if end > max_end:
                count += 1
max_end = end
return count

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Brute force	O(n²)	O(1)
Sort + max end ← optimal	O(n log n)	O(1)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No coverage	`[[1,2],[3,4]]`	No overlaps → count=2.
All covered	`[[1,10],[2,5],[3,4]]`	[2,5] and [3,4] covered by [1,10]. count=1.
Same start	`[[1,4],[1,2]]`	Sort: [1,4],[1,2]. [1,2] end=2 ≤ maxEnd=4 → covered.
Identical	`[[1,4],[1,4]]`	Second is covered by first. count=1.

⚠ Common Mistake: Sorting by start ascending and end ascending (default). This breaks same-start cases: [1,2] before [1,4] sets maxEnd=2, then [1,4] looks uncovered. Sort end descending on start ties to process the longer interval first.

← Back to Interval problems

LearningTree

LC 1288 · Remove Covered Intervals — Solution & Explanation | DSA Guide