{x}
blog image

Remove Covered Intervals

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 <= 105
  • All the given intervals are unique.

Solution Explanation for Remove Covered Intervals

This problem asks to find the number of intervals that are not covered by any other interval in a given list of intervals. The key insight is that we can sort the intervals cleverly to efficiently identify covered intervals.

Approach:

  1. Sorting: We sort the intervals based on their start times. If two intervals have the same start time, we prioritize the one with the smaller end time. This is crucial for the efficiency of the algorithm. The sorting ensures that we process intervals in increasing order of their start times.

  2. Iteration and Comparison: We iterate through the sorted intervals, keeping track of the interval with the largest end time encountered so far (pre). For each new interval, we compare its end time to the end time of pre.

    • If the current interval's end time is greater than pre's end time, it means this interval is not covered by pre (or any previous interval). We increment our counter of uncovered intervals and update pre to this current interval.
    • Otherwise, the current interval is covered by pre (or potentially an even earlier interval) and we ignore it.

  3. Return Value: The final count of uncovered intervals is returned.

Time Complexity Analysis:

  • Sorting the intervals takes O(N log N) time, where N is the number of intervals.
  • Iterating through the sorted intervals takes O(N) time.
  • Therefore, the overall time complexity is dominated by sorting, resulting in O(N log N).

Space Complexity Analysis:

  • The space complexity depends on the sorting algorithm used. In-place sorting algorithms (like merge sort or quicksort) have O(log N) space complexity due to the recursive call stack. However, if we use external sorting it will be O(N).
  • We use a constant amount of extra space to store the pre variable and the counter.
  • Therefore, the overall space complexity is O(log N) (or O(N) for external sorting).

Code Explanation (Python):

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1])) #Sort by start time, then descending end time.
        cnt, pre = 1, intervals[0] # Initialize count and 'previous' interval
        for e in intervals[1:]: #Iterate through remaining intervals
            if pre[1] < e[1]: #Check if current interval's end is greater than previous
                cnt += 1  #Increment count if not covered
                pre = e   #Update previous interval
        return cnt

The lambda function used in intervals.sort() defines a custom sorting key. It prioritizes sorting by the first element (start time) and then uses the negative of the second element (end time) for secondary sorting in descending order. This ensures that intervals with the same start time are ordered such that the one with the largest end time comes first.

The rest of the Python code directly implements the algorithm explained above. The Java, C++, and Go code follow the same approach, only differing in syntax. The core logic of sorting and comparing end times remains consistent across all languages.