# 1288. Remove Covered Intervals

## How std::vectors are ordered in C++

### Problem statement

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 <= 10^5`

.All the given intervals are unique.

### Solution 1: Bruteforce

For each interval `i`

, find if any other interval `j`

such that `j`

covers `i`

or `i`

covers `j`

then remove the smaller one from `intervals`

.

#### Example 1

For `intervals = [[1,4],[3,6],[2,8]]`

.

With interval

`i = [1,4]`

, there is no other interval`j`

such that covers`i`

or`j`

covers`i`

.With interval

`i = [3,6]`

, there is interval`j = [2,8]`

convering`i`

. Remove`[3,6]`

from`intervals`

.

Final `intervals = [[1,4],[2,8]]`

.

#### Code

```
#include <vector>
#include <iostream>
using namespace std;
inline bool isCovered(vector<int>& i, vector<int>& j) {
return j[0] <= i[0] && i[1] <= j[1];
}
int removeCoveredIntervals(vector<vector<int>>& intervals) {
int i = 0;
while (i < intervals.size() - 1) {
int j = i + 1;
bool erase_i = false;
while (j < intervals.size()) {
if (isCovered(intervals[i], intervals[j])) {
intervals.erase(intervals.begin() + i);
erase_i = true;
break;
} else if (isCovered(intervals[j], intervals[i])) {
intervals.erase(intervals.begin() + j);
} else {
j++;
}
}
if (!erase_i) {
i++;
}
}
return intervals.size();
}
int main() {
vector<vector<int>> intervals{{1,4},{3,6},{2,8}};
cout << removeCoveredIntervals(intervals) << endl;
intervals = {{1,4},{2,3}};
cout << removeCoveredIntervals(intervals) << endl;
}
```

```
Output:
2
1
```

#### Complexity

Runtime:

`O(N^3)`

, where`N = intervals.length`

.Extra space:

`O(1)`

.

### Solution 2: Using dictionary order

You might know how to look up words in a dictionary.

The word `apple`

appears before `candy`

in the dictionary because the starting letter `a`

of `apple`

appears before `c`

of `candy`

in the English alphabet.

And `apple`

appears after `animal`

since the next letter `p`

appears after `n`

.

The C++ Standard Library uses that dictionary order to compare two `std::vector`

s.

#### Example 1

Rewriting `intervals = [[1,4],[3,6],[2,8]]`

in dictionary order you get `intervals = [[1,4],[2,8],[3,6]]`

. In this order, the left bounds of the `intervals`

are sorted first.

If `intervals`

is sorted like that, you can avoid bruteforce in Solution 1 by a simpler algorithm.

**Check if each interval** `i`

covers or is covered by some of the previous ones.

Remember that the left bound of interval `i`

is always bigger than or equal to all left bounds of the previous ones. So,

`i`

is covered by some previous interval if the right bound of`i`

is less than some of the right bounds before.Otherwise

`i`

can only cover its exact previous one that has the same left bound.

#### Code

```
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int removeCoveredIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int count = 0;
int maxRight = -1;
int preLeft = -1;
for (auto& i : intervals) {
if (i[1] <= maxRight) { // i is covered by some previous interval
count++;
} else if (i[0] == preLeft) { // i covers its exact previous one
count++;
} else {
preLeft = i[0];
}
maxRight = max(maxRight, i[1]);
}
return intervals.size() - count;
}
int main() {
vector<vector<int>> intervals{{1,4},{3,6},{2,8}};
cout << removeCoveredIntervals(intervals) << endl;
intervals = {{1,4},{2,3}};
cout << removeCoveredIntervals(intervals) << endl;
}
```

```
Output:
2
1
```

#### Complexity

Runtime:

`O(NlogN)`

, where`N = intervals.length`

.Extra space:

`O(1)`

.

### Key takeaway

- Two
`std::vector`

s can be compared using the dictionary order.

*Thanks for reading. Feel free to share your thought about my content.*

*What is your approach? The problem was picked from* *leetcode.com**. You can submit your solution in any programming language and check the performance.*