Problem Description

Given a list of intervals, where each interval is represented as a pair [start, end], your task is to remove all intervals that are covered by another interval in the list. An interval [a, b] is considered covered by another interval [c, d] if and only if c <= a and b <= d. After removing all covered intervals, return the number of remaining intervals.

• Each interval is a pair of integers [start, end] with start < end.
• No two intervals with the same endpoints will appear.
• Intervals may overlap, be nested, or be disjoint.
• The input is an array intervals of length n where 1 <= n <= 1000.
• Your solution should only remove intervals that are strictly covered by another, not equal intervals.

Thought Process

To solve this problem, we need to determine which intervals are covered by others. At first glance, a brute-force approach comes to mind: for each interval, check against every other interval to see if it is covered. However, this would require nested loops and could be inefficient for larger inputs.

Instead, we can optimize by sorting the intervals. If we sort them by their start time (and for equal start times, by decreasing end time), it becomes easier to identify covered intervals by scanning through the sorted list and keeping track of the largest end point seen so far. This way, we can determine in a single pass if the current interval is covered by any previous one.

By shifting from brute-force comparison to a sorted traversal with tracking, we significantly reduce unnecessary checks and make the solution more efficient.

Solution Approach

• Step 1: Sort the intervals.
  • Sort by the start value in ascending order.
  • If two intervals have the same start, sort by end in descending order. This ensures that longer intervals come before shorter, nested ones.
• Step 2: Initialize a variable to track the farthest end point seen so far.
  • Let’s call it max_end and set it to 0 initially.
• Step 3: Iterate through the sorted intervals.
  • For each interval [start, end]:
  • If end <= max_end, the interval is covered by a previous interval and should not be counted.
  • Otherwise, it is not covered, so increment your count and update max_end to end.
• Step 4: Return the count of non-covered intervals.

This approach efficiently finds and removes covered intervals in a single pass after sorting.

Example Walkthrough

Example Input: intervals = [[1,4],[3,6],[2,8]]

1. Sort the intervals:
   After sorting by start ascending and end descending, we get:
   [[1,4], [2,8], [3,6]]
2. Initialize max_end = 0 and count = 0.
3. First interval [1,4]:
   • 4 > max_end (0) → not covered.
   • Increment count to 1. Update max_end = 4.
4. Second interval [2,8]:
   • 8 > max_end (4) → not covered.
   • Increment count to 2. Update max_end = 8.
5. Third interval [3,6]:
   • 6 <= max_end (8) → covered by previous interval.
   • Do not increment count.
6. Result: 2 intervals remain after removing covered intervals.

Code Implementation

class Solution:
    def removeCoveredIntervals(self, intervals):
        # Sort by start asc, end desc
        intervals.sort(key=lambda x: (x[0], -x[1]))
        count = 0
        max_end = 0
        for start, end in intervals:
            if end > max_end:
                count += 1
                max_end = end
        return count
      

class Solution {
public:
    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 count = 0, maxEnd = 0;
        for (const auto& interval : intervals) {
            if (interval[1] > maxEnd) {
                ++count;
                maxEnd = interval[1];
            }
        }
        return count;
    }
};
      

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 count = 0, maxEnd = 0;
        for (int[] interval : intervals) {
            if (interval[1] > maxEnd) {
                count++;
                maxEnd = interval[1];
            }
        }
        return count;
    }
}
      

var removeCoveredIntervals = function(intervals) {
    intervals.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    let count = 0, maxEnd = 0;
    for (const [start, end] of intervals) {
        if (end > maxEnd) {
            count++;
            maxEnd = end;
        }
    }
    return count;
};
      

Time and Space Complexity

• Brute-force Approach:
  • For each interval, check against every other interval to see if it is covered.
  • This results in O(n^2) time complexity.
  • Space complexity is O(1) (not counting input).
• Optimized Approach (Sorting + Single Scan):
  • Sorting the intervals takes O(n \log n) time.
  • Scanning through the intervals takes O(n) time.
  • So the overall time complexity is O(n \log n).
  • Space complexity is O(1) if sorting is in-place, otherwise O(n) for the sort.

Summary

The key insight in solving the Remove Covered Intervals problem efficiently is to sort the intervals in a way that simplifies the comparison of coverage. By sorting first by start (ascending) and then by end (descending), we make it possible to detect covered intervals with a single forward scan, tracking the farthest end point seen so far. This approach is both elegant and efficient, reducing the problem from a quadratic brute-force check to a linear scan after sorting, and is easy to implement in any major programming language.