## Problem

LeetCode 1288: Remove Covered Intervals (Medium)

**Problem statement**: Given a list of intervals, return the number of intervals that are not covered by another interval in the list.

For this problem, think of an interval as a segment of the number line with integer starting and ending points. For example, the interval $(-1, 1)$ is a segment of length $2$ centered at $0$.

Interval $(c,d)$ *covers* interval $(a,b)$ iff $c \leq a$ and $b \leq d$. Intuitively, this means that no point on $(a,b)$ is outside of the range covered by $(c,d)$.

Note that if one interval’s end point is the same as another interval’s start point, neither interval covers the other. For example, intervals $(0,2)$ and $(2,4)$ would contribute two intervals to the count. But $(0,2)$ and $(1,2)$ would only contribute one interval to the count, since the first interval covers the second. In a third case, $(0,2)$ and $(1,3)$ would count as two intervals. Although the intervals overlap, neither interval completely covers the other.

## Solution

The solution described here is based on this solution by lee215, a well-known contributor to the LeetCode discussion forums.

**Algorithm**

- Sort the intervals by start position. This allows us to make one pass through the list without backtracking or using any data structure besides an array.
- Maintain a
*comparison interval*$(c,d)$ that stores the most recent interval that is*not*covered by another interval. Note that $(c,d)$ is not necessarily an interval in the input list. - For each interval $(a,b)$ in the input list:
- If $a > c$ and $b > d$, then some of $(a,b)$ is to the right of comparison interval $(c,d)$, and some of comparison interval $(c,d)$ is to the left of $(a,b)$. This means neither interval completely covers the other. Therefore, we can increment the interval count by one. We also need to let $c=a$ to advance the comparison interval start point.
- Let $d=\max(d,b)$ to advance the comparison interval end point.

- Return the interval count.

**Notes**

One way to see why this algorithm works is to consider all the ways that interval $(a,b)$ and comparison interval $(c,d)$ can be positioned relative to each other. For the starting endpoints of each interval, the possibilities are $a<c$, $a=c$, and $a>c$. Similarly, for the ending endpoints, we have $b<d$, $b=d$, and $b>d$. Since there are three possibilities for each of the two endpoints, there are a total of $3 \times 3 = 9$ combinations.

But because we start the algorithm by sorting the intervals by start point, we can eliminate $a<c$, since each interval must start at least even with the previous interval (i.e., the start points are nondecreasing). This means there are only $2 \times 3 = 6$ cases that can occur. Here are those cases:

(1) $a>c$ and $b>d$

```
c ---------- d
a ---------- b
```

This is the configuration detected by the `if`

statement in the algorithm. Neither interval covers the other, so we increment `count`

and $(a,b)$ becomes the new comparison interval.

(2) $a>c$ and $b=d$

```
c ---------- d
a -------- b
```

$(a,b)$ is completely covered by $(c,d)$, so we skip it without incrementing `count`

.

(3) $a>c$ and $b<d$

```
c ---------- d
a ------ b
```

This is a similar configuration to (2). $(a,b)$ is completely covered.

(4) $a=c$ and $b>d$

```
c ---------- d
a ------------ b
```

As with the other cases, we don’t go into the `if`

block so we don’t increment `count`

for this case. But this time it’s because the new interval $(a,b)$ covers the comparison interval $(c,d)$ (the reverse of cases (2) and (3)). This is why it’s important to set $d=\max(d,b)$ outside the `if`

block. Even when there’s not a new interval to count, we need the right endpoint of the comparison interval to be as far right as possible.

(5) $a=c$ and $b=d$

```
c ------------ d
a ------------ b
```

The new interval is identical to the comparison interval, so we don’t count it.

(6) $a=c$ and $b<d$

```
c ------------ d
a ---------- b
```

This is similar to (3) and (4). $(a,b)$ is completely covered, so we don’t count it.

After considering all six cases, we can see that we only need to count a new interval in one case, the first one. In the other cases, all we need to do is possibly adjust the right endpoint of the comparison interval.

**Code**

Remove Covered Intervals on GitHub

**LeetCode Model Solutions**

*I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.*