Remove Covered Intervals solution and explanation
Google
9 more videos on this problem
Remove Covered Intervals - Leetcode 1288 - PythonNeetCode · 11:56 · 17K views
Remove Covered Intervals | 3 Detailed Approaches | Dry Runs | Leetcode 1288 | codestorywithMIKcodestorywithMIK · 32:43 · 6K views
Remove Covered Intervals | Leetcode 1288 | Live coding session 🔥🔥🔥| Greedy | Sorting TC O(nlogn)Coding Decoded · 7:39 · 1K views
Remove Covered Intervals | Leet code 1288 | Theory explained + Python codeSai Anish Malla · 11:14 · 1K views
Leetcode 1288: Remove Covered IntervalsAlgorithms Casts · 14:10 · 616 views
1288. Remove Covered Intervals | LEETCODE | SORTINGcode Explainer · 11:20 · 402 views
Daily Leetcode #187: Oct 04, 2020 - 1288. Remove Covered IntervalsProgramming Live with Larry · 5:58 · 365 views
Remove Covered Intervals | LeetCode 1288 | October LeetCode Challenge | Day 4Learn Code Repeat · 11:29 · 364 views
1288. Remove Covered Intervals | Leetcode Daily - PythonLeetcode Daily · 3:48 · 328 views
Leetcode 1288 Remove Covered IntervalsRen Zhang · 12:14 · 289 views
The problem
Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
Return the number of remaining intervals.
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
Example 2:
Input: intervals = [[1,4],[2,3]] Output: 1
Constraints:
1 <= intervals.length <= 1000intervals[i].length == 20 <= li < ri <= 105- All the given intervals are unique.
Approach overview
Problem Overview: You are given a list of intervals where each interval is represented as [start, end]. An interval is considered covered if another interval fully contains it. The task is to remove all covered intervals and return the number of remaining intervals.
Approach 1: Graph-Based Comparison (Implicit Graph) (O(n²) time, O(1) extra space)
Treat every interval as a node and check coverage relationships between all pairs. For each interval i, iterate through every other interval j. If j.start ≤ i.start and j.end ≥ i.end, interval i is covered and should not be counted. This brute-force comparison effectively builds an implicit coverage graph without storing edges. The method is straightforward and helps you reason about the definition of coverage, but the nested iteration leads to O(n²) time complexity. Space stays O(1) because only counters and temporary variables are used.
Approach 2: Sort by Start, End Descending (O(n log n) time, O(1) space)
The optimal solution relies on sorting. Sort intervals by start in ascending order. When two intervals share the same start, sort by end in descending order. This ordering guarantees that larger covering intervals appear before the smaller ones they might contain.
After sorting, scan the array once while tracking the maximum end value seen so far. If the current interval's end is less than or equal to that maximum, it is covered by a previous interval. Otherwise, it is a valid interval that should be counted, and the maximum end gets updated. Because sorting groups potential coverings together, a single linear pass is enough to detect coverage relationships.
This approach combines array traversal with sorting order to eliminate the need for pairwise comparisons. Sorting costs O(n log n), and the scan is O(n). No additional data structures are required beyond a few variables, so extra space remains O(1) (ignoring sort implementation details).
Recommended for interviews: The sorting approach is the expected solution. It shows you recognize that ordering intervals can simplify containment checks and reduce the complexity from O(n²) to O(n log n). Explaining the brute-force comparison first demonstrates clear understanding of the coverage rule, while the optimized sorting strategy shows strong algorithmic thinking using sorting and interval scanning patterns.
Approach 1: Sorting by Start and then by End Descending
First, sort the intervals by their starting point. If two intervals have the same start, sort them by their ending point in descending order. This helps in ensuring that when you iterate, you can simply keep a check on the maximum end encountered and compare each interval to determine if it is covered.
def removeCoveredIntervals(intervals):
intervals.sort(key=lambda x: (x[0], -x[1]))
remaining = 0
prev_end = 0
for _, end in intervals:
if end > prev_end:
remaining += 1
prev_end = end
return remainingimport 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 remaining = 0, prevEnd = 0;
for (int[] interval : intervals) {
if (interval[1] > prevEnd) {
remaining++;
prevEnd = interval[1];
}
}
return remaining;
}
}#include <vector>
#include <algorithm>
using namespace std;
int removeCoveredIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
});
int remaining = 0, prevEnd = 0;
for (const auto& interval : intervals) {
if (interval[1] > prevEnd) {
remaining++;
prevEnd = interval[1];
}
}
return remaining;
}var removeCoveredIntervals = function(intervals) {
intervals.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
let remaining = 0, prevEnd = 0;
for (let [, end] of intervals) {
if (end > prevEnd) {
remaining++;
prevEnd = end;
}
}
return remaining;
};#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *intA = *(int**)a;
int *intB = *(int**)b;
if (intA[0] != intB[0])
return intA[0] - intB[0];
return intB[1] - intA[1];
}
int removeCoveredIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
qsort(intervals, intervalsSize, sizeof(intervals[0]), compare);
int remaining = 0, prevEnd = 0;
for (int i = 0; i < intervalsSize; ++i) {
if (intervals[i][1] > prevEnd) {
remaining++;
prevEnd = intervals[i][1];
}
}
return remaining;
}using System;
using System.Collections.Generic;
public class Solution {
public int RemoveCoveredIntervals(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int remaining = 0, prevEnd = 0;
foreach (var interval in intervals) {
if (interval[1] > prevEnd) {
remaining++;
prevEnd = interval[1];
}
}
return remaining;
}
}In Python, sorting is done using the sort() method with a custom key that first checks the starting point and then the ending point in descending order if starts are equal. The counting mechanism is similar to the previous implementations, keeping a count of uncovered intervals.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we use a constant number of extra variables.
Approach 2: Graph-Based Approach (Implicit Graph)
Conceptually, treat each pair of intervals as a directed edge if one interval is covering another. Such implicit graph construction helps identify covered intervals. You process over this graph to recognize unique intervals not covered by others. This approach may be non-trivial compared to the sorting technique, but it provides a different perspective.
def is_covered(a, b):
return b[0] <= a[0] and a[1] <= b[1]
def removeCoveredIntervalsGraph(intervals):
remaining = len(intervals)
covered = [False] * len(intervals)
for i in range(len(intervals)):
for j in range(len(intervals)):
if i != j and not covered[i] and is_covered(intervals[i], intervals[j]):
covered[i] = True
remaining -= 1
break
return remainingimport java.util.*;
class Solution {
private boolean isCovered(int[] a, int[] b) {
return b[0] <= a[0] && a[1] <= b[1];
}
public int removeCoveredIntervalsGraph(int[][] intervals) {
int remaining = intervals.length;
boolean[] covered = new boolean[intervals.length];
Arrays.fill(covered, false);
for (int i = 0; i < intervals.length; ++i) {
for (int j = 0; j < intervals.length; ++j) {
if (i != j && !covered[i] && isCovered(intervals[i], intervals[j])) {
covered[i] = true;
--remaining;
break;
}
}
}
return remaining;
}
}#include <vector>
using namespace std;
bool isCovered(const vector<int>& a, const vector<int>& b) {
return b[0] <= a[0] && a[1] <= b[1];
}
int removeCoveredIntervalsGraph(vector<vector<int>>& intervals) {
int remaining = intervals.size();
vector<bool> covered(intervals.size(), false);
for (int i = 0; i < intervals.size(); ++i) {
for (int j = 0; j < intervals.size(); ++j) {
if (i != j && !covered[i] && isCovered(intervals[i], intervals[j])) {
covered[i] = true;
--remaining;
break;
}
}
}
return remaining;
}var removeCoveredIntervalsGraph = function(intervals) {
const isCovered = (a, b) => b[0] <= a[0] && a[1] <= b[1];
let remaining = intervals.length;
const covered = new Array(intervals.length).fill(false);
for (let i = 0; i < intervals.length; ++i) {
for (let j = 0; j < intervals.length; ++j) {
if (i !== j && !covered[i] && isCovered(intervals[i], intervals[j])) {
covered[i] = true;
remaining--;
break;
}
}
}
return remaining;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int isCovered(int* intervalA, int* intervalB) {
return intervalB[0] <= intervalA[0] && intervalA[1] <= intervalB[1];
}
int removeCoveredIntervalsGraph(int** intervals, int intervalsSize, int* intervalsColSize) {
int remaining = intervalsSize;
bool* covered = calloc(intervalsSize, sizeof(bool));
for (int i = 0; i < intervalsSize; ++i) {
for (int j = 0; j < intervalsSize; ++j) {
if (i != j && !covered[i] && isCovered(intervals[i], intervals[j])) {
covered[i] = true;
--remaining;
break;
}
}
}
free(covered);
return remaining;
}using System;
public class Solution {
private bool IsCovered(int[] a, int[] b) {
return b[0] <= a[0] && a[1] <= b[1];
}
public int RemoveCoveredIntervalsGraph(int[][] intervals) {
int remaining = intervals.Length;
bool[] covered = new bool[intervals.Length];
for (int i = 0; i < intervals.Length; ++i) {
for (int j = 0; j < intervals.Length; ++j) {
if (i != j && !covered[i] && IsCovered(intervals[i], intervals[j])) {
covered[i] = true;
--remaining;
break;
}
}
}
return remaining;
}
}The Python function evaluates potential graph connections implying coverage. 'Covered' boolean list identifies intervals that are enveloped (becoming non-essential), hence they are decrementally ignored in the output result.
Time Complexity: O(n^2) since it relies on two-level checks.
Space Complexity: O(n) by maintaining 'covered' indicators for each interval.
Approach 3: Sorting
We can sort the intervals in ascending order by their left endpoints, and if the left endpoints are the same, sort them in descending order by their right endpoints.
After sorting, we can traverse the intervals. If the right endpoint of the current interval is greater than the previous right endpoint, it means the current interval is not covered, and we increment the answer by one.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.
function removeCoveredIntervals(intervals: number[][]): number {
intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
let ans = 0;
let pre = -Infinity;
for (const [_, cur] of intervals) {
if (cur > pre) {
++ans;
pre = cur;
}
}
return ans;
}func removeCoveredIntervals(intervals [][]int) (ans 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]
})
pre := math.MinInt32
for _, e := range intervals {
cur := e[1]
if cur > pre {
ans++
pre = cur
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting by Start and then by End Descending | Time Complexity: O(n log n) due to sorting. |
| Graph-Based Approach (Implicit Graph) | Time Complexity: O(n^2) since it relies on two-level checks. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph-Based Comparison (Implicit Graph) | O(n²) | O(1) | Useful for understanding the coverage definition or when constraints are very small. |
| Sort by Start, End Descending | O(n log n) | O(1) | Optimal general solution. Preferred in interviews and large input sizes. |
Frequently asked questions
Is Remove Covered Intervals easy or hard?
Remove Covered Intervals is rated Medium difficulty. The coverage condition is simple, but recognizing that sorting by start and end order allows a single linear scan requires familiarity with interval and greedy patterns.
Remove Covered Intervals Python/Java solution
In Python or Java, implement a custom sort that orders intervals by start ascending and end descending. After sorting, iterate through the intervals while maintaining a variable for the largest end encountered and count intervals that are not covered.
How to solve Remove Covered Intervals in O(n)?
Pure O(n) time is generally not possible because intervals must be ordered to detect coverage efficiently. Sorting by start ascending and end descending reduces the problem to a single linear scan after sorting. The total complexity becomes O(n log n).
What is the best approach for Remove Covered Intervals?
The best approach sorts intervals by start ascending and end descending, then scans once while tracking the maximum end seen so far. If the current interval's end is less than or equal to the maximum end, it is covered. This method runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Remove Covered Intervals asked at Google/Amazon/Meta?
Interval and sorting problems like Remove Covered Intervals frequently appear in interviews at companies such as Google, Amazon, and Meta. They test understanding of interval ordering, greedy scanning, and how sorting can eliminate unnecessary comparisons.
What data structure is used in Remove Covered Intervals?
The problem mainly uses arrays and sorting. Intervals are stored in an array, sorted by custom comparator rules, and then scanned while tracking the maximum end value seen so far.
What is the time complexity of Remove Covered Intervals?
The optimal solution runs in O(n log n) time because the intervals must be sorted first. After sorting, a single linear scan checks whether each interval is covered by comparing end values. The brute-force comparison approach takes O(n²) time.