# Remove Covered Intervals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-covered-intervals)
Canonical: https://scaleengineer.com/dsa/problems/remove-covered-intervals
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 <= 1000`
* `intervals[i].length == 2`
* `0 <= li < ri <= 105`
* All the given intervals are **unique**.

# Approaches
## Brute Force Comparison
This approach involves comparing every interval with every other interval in the list. For each interval, we check if it is 'covered' by any other interval according to the given definition.
**Time:** O(N^2), where N is the number of intervals. The nested loops lead to a quadratic time complexity as each interval is compared with every other interval. · **Space:** O(N) to store the `removed` boolean array.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large inputs due to the quadratic time complexity.
### Explanation
We can solve this problem by iterating through each interval and then, in a nested loop, comparing it against every other interval.

We use a boolean array, `removed`, of the same size as the input `intervals` array, to keep track of which intervals have been found to be covered.

The outer loop selects an interval `i`, and the inner loop selects another interval `j`.

Inside the inner loop, we check if interval `i` is covered by interval `j`. The condition for an interval `[a, b)` to be covered by `[c, d)` is `c <= a` and `b <= d`.

If interval `i` is covered by `j`, we mark `removed[i]` as `true` and can break the inner loop for the current `i`, since we only need to find one interval that covers it.

After the loops complete, we count the number of `false` values in the `removed` array, which corresponds to the number of remaining, non-covered intervals. Alternatively, we can count the `true` values and subtract from the total number of intervals.

```java
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        int n = intervals.length;
        boolean[] removed = new boolean[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                // Check if interval i is covered by interval j
                // interval i = [intervals[i][0], intervals[i][1])
                // interval j = [intervals[j][0], intervals[j][1])
                if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) {
                    removed[i] = true;
                    break; // Found a covering interval, move to the next i
                }
            }
        }

        int remainingCount = 0;
        for (int i = 0; i < n; i++) {
            if (!removed[i]) {
                remainingCount++;
            }
        }
        return remainingCount;
    }
}
```
### Algorithm
- Initialize a boolean array `removed` of size `n` (number of intervals) to all `false`.
- Iterate through the intervals with an index `i` from `0` to `n-1`.
- For each interval `i`, iterate through the intervals with an index `j` from `0` to `n-1`.
- If `i` is the same as `j`, skip the comparison.
- Check if interval `i` (`[a, b)`) is covered by interval `j` (`[c, d)`) using the condition `c <= a` and `b <= d`.
- If interval `i` is covered, set `removed[i] = true` and break the inner loop.
- After the loops, count the number of `false` entries in the `removed` array. This count is the result.

## Greedy Approach with Sorting
A more efficient approach is to first sort the intervals. By sorting them in a specific way, we can determine if an interval is covered in a single pass. We sort the intervals primarily by their start points in ascending order. If two intervals have the same start point, we sort them by their end points in descending order.
**Time:** O(N log N), where N is the number of intervals. The dominant operation is sorting the array. · **Space:** O(log N) or O(N), depending on the space complexity of the sorting algorithm used. In Java, `Arrays.sort` for objects uses Timsort, which can take up to O(N) space in the worst case.
**Pros:** Significantly more efficient than the brute-force approach.; The logic is elegant once the sorting strategy is understood.
**Cons:** Requires modifying the input array by sorting it, or using extra space to store a sorted copy.; The sorting logic (especially the secondary sort key) is crucial and might not be immediately obvious.
### Explanation
The key insight is that after sorting, we can process the intervals in a way that simplifies the check for covered intervals.

The sorting criteria are:
1.  Sort by the start point in ascending order.
2.  If start points are equal, sort by the end point in *descending* order.

This sorting strategy ensures that if we are at an interval `i`, any subsequent interval `j` cannot cover `i`. This is because either `intervals[j][0] > intervals[i][0]`, or if `intervals[j][0] == intervals[i][0]`, then `intervals[j][1] <= intervals[i][1]`. In neither case can `j` cover `i`.

Therefore, an interval can only be covered by an interval that appeared *before* it in the sorted list.

We can iterate through the sorted intervals and keep track of the maximum end point (`maxEnd`) seen so far.

An interval `[start, end]` is covered if its end point `end` is less than or equal to `maxEnd`. If `end > maxEnd`, the interval is not covered by any previous one, so we count it and update `maxEnd` to this new, larger end point.

```java
import java.util.Arrays;

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // Sort by start point ascending. If start points are equal,
        // sort by end point descending.
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return b[1] - a[1];
            }
        });

        int count = 0;
        int maxEnd = 0;

        for (int[] interval : intervals) {
            // If the current interval extends beyond the max end point seen so far,
            // it is not covered.
            if (interval[1] > maxEnd) {
                count++; // This is a new, non-covered interval.
                maxEnd = interval[1]; // Update the max end point.
            }
            // Otherwise, the interval is covered by a previous one, so we ignore it.
        }

        return count;
    }
}
```
### Algorithm
- Sort the `intervals` array. The primary sorting key is the start point (ascending), and the secondary key is the end point (descending).
- Initialize a counter `count` to `0` and a variable `maxEnd` to `0`.
- Iterate through the sorted intervals `[start, end]`.
- For each interval, check if its `end` is greater than `maxEnd`.
- If `end > maxEnd`, it means this interval is not covered by any previous one. Increment `count` and update `maxEnd = end`.
- If `end <= maxEnd`, the interval is covered, so we do nothing.
- Return `count` after the loop finishes.

# Solutions
### Java

```java
class Solution { public int removeCoveredIntervals ( int [][] intervals ) { Arrays . sort ( intervals , ( a , b ) -> a [ 0 ] - b [ 0 ] == 0 ? b [ 1 ] - a [ 1 ] : a [ 0 ] - b [ 0 ]); int [] pre = intervals [ 0 ]; int cnt = 1 ; for ( int i = 1 ; i < intervals . length ; ++ i ) { if ( pre [ 1 ] < intervals [ i ][ 1 ]) { ++ cnt ; pre = intervals [ i ]; } } return cnt ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} intervals * @return {number} */ var removeCoveredIntervals =
  function (intervals) {
    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;
  };

```

### CPP

```cpp
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 ] ? b [ 1 ] < a [ 1 ] : a [ 0 ] < b [ 0 ]; }); int cnt = 1 ; vector < int > pre = intervals [ 0 ]; for ( int i = 1 ; i < intervals . size (); ++ i ) { if ( pre [ 1 ] < intervals [ i ][ 1 ]) { ++ cnt ; pre = intervals [ i ]; } } return cnt ; } };
```

### Python

```python
class Solution : def removeCoveredIntervals ( self , intervals : List [ List [ int ]]) -> int : intervals . sort ( key = lambda x : ( x [ 0 ], - x [ 1 ])) cnt , pre = 1 , intervals [ 0 ] for e in intervals [ 1 :]: if pre [ 1 ] < e [ 1 ]: cnt += 1 pre = e return cnt
```