Remove Covered Intervals — Solution in Python, Java & C++
Remove Covered Intervals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Covered Intervals is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of intervals where intervals[i] = [l, r], remove every interval that is covered by another one, then return the number of intervals left.
Interval [a, b) is covered by [c, d) when c <= a and b <= d.
Example 1
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: [3,6] is covered by [2,8].
Example 2
Input: intervals = [[1,4],[2,3]]
Output: 1
Example 3
Input: intervals = [[0,10],[5,12]]
Output: 2
Constraints
1 <= intervals.length <= 300 <= l < r <= 1000
Hints for Remove Covered Intervals
Hint 1
Sort by left endpoint ascending; ties must break by right endpoint descending.
Hint 2
That tie-break puts a covering interval before the ones it swallows.
Hint 3
Then keep an interval only when its right endpoint exceeds the largest right endpoint seen so far.
How to solve Remove Covered Intervals
Sort by left ascending, ties by right descending; then an interval survives only if its right endpoint exceeds the largest right endpoint seen so far.
Approach
- Sort by
(l, -r). - Walk with
right = -1; whenr > right, count it and setright = r.
Why it works
After sorting, every earlier interval starts at or before the current one, so the current interval is covered exactly when some earlier interval also reaches at least as far right. The tie-break puts the covering interval first when lefts are equal.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Ties by right ascending would count the covered interval before its cover.
Reference solution
Python
def removeCoveredIntervals(intervals) -> int:
ordered = sorted(intervals, key=lambda p: (p[0], -p[1]))
count = 0
right = -1
for l, r in ordered:
if r > right:
count += 1
right = r
return countJava
public static int removeCoveredIntervals(int[][] intervals) {
int[][] s = intervals.clone();
Arrays.sort(s, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int count = 0, right = -1;
for (int[] iv : s) {
if (iv[1] > right) {
count++;
right = iv[1];
}
}
return count;
}C++
int removeCoveredIntervals(vector<vector<int>>& intervals) {
vector<vector<int>> s = intervals;
sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
return a[1] > b[1];
});
int count = 0, right = -1;
for (const auto& iv : s) {
if (iv[1] > right) {
count++;
right = iv[1];
}
}
return count;
}JavaScript
var removeCoveredIntervals = function(intervals) {
const sorted = intervals.slice().sort(function(a, b) {
return a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1];
});
let count = 0, right = -1;
for (let i = 0; i < sorted.length; i++) {
if (sorted[i][1] > right) {
count++;
right = sorted[i][1];
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms