> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/medium/remove-covered-intervals.md).

# Remove Covered Intervals

## [Remove Covered Intervals](https://leetcode.com/problems/remove-covered-intervals)

Given a list of `intervals`, remove all intervals that are covered by another interval in the list.

Interval `[a,b)` is covered by interval `[c,d)` if and only if `c <= a` and `b <= d`.

After doing so, 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
```

**Example 3:**

```

Input: intervals = [[0,10],[5,12]]
Output: 2
```

**Example 4:**

```

Input: intervals = [[3,10],[4,10],[5,11]]
Output: 2
```

**Example 5:**

```

Input: intervals = [[1,2],[1,4],[3,4]]
Output: 1
```

**Constraints:**

* `1 <= intervals.length <= 1000`
* `intervals[i].length == 2`
* `0 <= intervals[i][0] < intervals[i][1] <= 10^5`
* All the intervals are **unique**.

## Solutions

### 🧠 Cpp

```cpp
class Solution
{
    enum {START, END};

public:

    //O(n log n) solution: sort + 1 pass
    int removeCoveredIntervals(vector<vector<int>>& intervals)
    {
        std::sort(begin(intervals), end(intervals),
                 [](auto a, auto b)
                 {
                   return a[END] == b[END] ? a[START] > b[START] : a[END] < b[END];  
                 }
                 );

        //copy data to list for O(1) erasure
        std::list<vector<int>> i_vals(begin(intervals), end(intervals));


        //ENDs is already sorted, so next element has end >= than prev
        //only thing is to check the start of the interval, if prev has START > next start
        //then it's covered
        for(auto iter = begin(i_vals); iter != prev(end(i_vals));)
        {
            if((*iter)[START] >= (*next(iter))[START])
            {
                iter = i_vals.erase(iter);
                if(iter != begin(i_vals))
                    advance(iter, -1);
            }
            else
                ++iter;
        }

        return i_vals.size();
    }
};
```