Remove Covered Intervals

Share

Given a list of intervals, remove all intervals covered by another interval. An interval [a,b] is covered by [c,d] if c <= a and b <= d. Return the number of remaining intervals.

Example 1
Input: [[1,4],[3,6],[2,8]] → Output: 2
Example 2
Input: [[1,4],[2,3]] → Output: 1

Solution Approach

Sort by start ascending, then by end descending (so for equal starts, longer interval comes first). Keep track of the maximum end seen so far. If current end <= maxEnd, current interval is covered.

  • Sort: by start asc, then end desc.
  • Track maxEnd = 0, count = 0.
  • For each interval: if end > maxEnd, count++, maxEnd = end (not covered).
  • Return count.
Java
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;
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(1)