Remove Covered Intervals
Medium · Intervals · Array · Sorting · Intervals
Problem
You are given a list intervals of distinct intervals, where intervals[i] = [l_i, r_i] stands for the half-open range [l_i, r_i). Interval [a, b) is *covered* by interval [c, d) when c <= a and b <= d.
Remove every interval that is covered by some other interval in the list, and return how many intervals remain.
Examples
Input: intervals = [[1,6],[2,5],[4,8],[4,7]] Output: 2
[2, 5] lies inside [1, 6] and [4, 7] inside [4, 8], leaving two.
Input: intervals = [[1,3],[2,4]] Output: 2
They overlap, but neither holds the other.
Input: intervals = [[3,9],[3,5],[5,9]] Output: 1
Both shorter intervals lie inside [3, 9], including the one sharing its start.
Constraints
- 1 <= intervals.length <= 1000
- intervals[i].length == 2
- 0 <= l_i < r_i <= 10^5
- all intervals are distinct
Approaches
- Baseline: check every pair — time O(n²), space O(1)
Follow-up
After the sort, one running maximum decides everything. The use cases return the surviving intervals themselves and count the intervals that contain at least one other.
Related problems
Start free on Cariara · Coding problems · System design studio
