Remove Covered Intervals

Problem Description

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.

Key Insights

• An interval is covered if there exists another interval that starts before it and ends after it.
• Sorting the intervals by their starting point helps to simplify the comparison.
• A greedy approach can be used to keep track of the non-covered intervals as we iterate through the sorted list.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting step. Space Complexity: O(1) - we can solve the problem using a constant amount of extra space.

Solution

To solve the problem, we can follow these steps:

1. Sort the intervals based on their starting points (and ending points for tie-breaking).
2. Initialize a variable to track the end of the last added interval.
3. Iterate through the sorted intervals, adding an interval to the result only if it is not covered by the last added interval.
4. Count the number of non-covered intervals and return that count.

Code Solutions