Solution: Remove Covered Intervals

Statement

Given an array of intervals, where each interval is represented as intervals[i] $= [l_i, r_i)$ (indicating the range from $l_i$ to $r_i$, inclusive of $l_i$ and exclusive of $r_i$), remove all intervals that are completely covered by another interval in the list. Return the count of intervals that remain after removing the covered ones.

Note: An interval $[a, b)$ is considered covered by another interval $[c, d)$ if and only if $c <= a$ and $b <= d$.

Constraints:

• $1 <=$ intervals.length $<= 1000$

• intervals[i].length $== 2$

• $0 <= l_i < r_i <= 10^5$

• All the given intervals are unique.

Solution

The first step is to simplify the process by sorting the intervals. Sorting by the start point in ascending order is straightforward and simplifies the iteration process. However, an important edge case arises when two intervals share the same start point. In such scenarios, sorting solely by the start point would fail to correctly identify covered intervals. To handle this, we sort intervals with the same start point by their endpoint in descending order, ensuring that longer intervals come first. This sorting strategy guarantees that if one interval covers another, it will be positioned earlier in the sorted list. Once the intervals are sorted, we iterate through them while keeping track of the maximum endpoint seen so far. If the current interval’s end point exceeds this maximum, it is not covered, so we increment the count and update the maximum end. The interval is covered and skipped if the endpoint is less than or equal to the maximum. After completing the iteration, the final count reflects the remaining non-covered intervals.

Now, let’s look at the solution steps below:

• If the start points are the same, sort the intervals by the start point in ascending order, otherwise, sort by the endpoint in descending order to prioritize longer intervals.

• Initialize the count with zero to track the remaining (non-covered) intervals.

• Initialize prevEnd with zero to track the maximum end value we’ve seen..

• Start iterating through intervals for each interval [start, end] in the sorted list:

  • If end > prevEnd, any previous interval does not cover the interval.

    • Increment count by $1$.

    • Update prevEnd to end.

  • Else:

    • A previous interval covers the interval, so we skip it.

• After iterating through all the intervals, the return count is the final value, representing the remaining intervals.

Let’s look at the following illustration to get a better understanding of the solution: