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.