Domain 2MediumMEDIUM

Remove Covered Intervals

Sort intervals by start time ascending and end time descending, then iterate to count non-covered intervals using a running maximum of end times.

Domain: medium•Updated: 2026-09-14
#Greedy#Sorting#$O(N log N)$#$O(1)

Problem Breakdown

We are given an array of intervals, where each interval is represented as [start, end]. The goal is to return the number of remaining intervals after removing all that are “covered” by at least one other interval. An interval AA covers interval BB if and only if A.start≤B.startA.start \le B.start AND A.end≥B.endA.end \ge B.end.

Inputs: A list of lists, where each inner list contains two integers [start, end]. Outputs: An integer representing the count of non-covered intervals. Constraints & Edge Cases:

  • Empty Input: Constraints state length ≥1\ge 1, so we don’t need to handle empty arrays explicitly in code logic (though good practice).
  • Duplicates/Uniqueness: The problem states all intervals are unique, but our algorithm should naturally handle duplicates if they existed. If two identical intervals exist, one covers the other; sorting handles this by ensuring only one counts or both count depending on strict inequality checks. Here we use end > max_end, so strictly greater ensures distinctness in counting logic for same bounds (though constraints say unique).
  • Overlapping: Intervals can overlap partially or fully. The sort order is critical here to handle overlaps efficiently without nested loops.

Intuition

A brute-force approach would compare every interval with every other interval (O(N2)O(N^2)) to check coverage conditions. While N=1000N=1000 allows this, a senior engineer should aim for an optimal solution using sorting and greedy logic.

Key Insight: If we sort the intervals by their start time in ascending order, any potential covering interval must appear before or at the same index as the current interval (since it needs to have started earlier). By maintaining a running maximum of end times (max_end) seen so far during iteration:

  1. We know that all previous intervals satisfy start_prev <= start_curr.
  2. If an interval’s end is less than or equal to the current max_end, it means there exists at least one previously processed interval (which started earlier) that ends later, thus covering the current interval completely.
  3. To handle cases where intervals share the same start time correctly (e.g., [1,4] and [1,2]), we must sort by end time in descending order for ties. This ensures the widest interval is processed first to set a high max_end, allowing subsequent narrower intervals starting at the same point to be identified as covered immediately.

Approach

  1. Sort: Sort the input list primarily by start time ascending, and secondarily by end time descending (for equal starts).
  2. Initialize: Set a counter for remaining intervals (count = 0) and track the furthest right boundary seen so far (max_end). Initialize max_end to -1 or handle the first element separately since inputs are non-negative.
  3. Iterate: Loop through each interval [start, end]:
    • If end > max_end, this interval is not covered by any previous one (since all previous ones ended ≤\le max_end). Increment count and update max_end to the current end.
    • Otherwise (end <= max_end), it is covered. Do nothing for the counter, but implicitly we don’t need to update max_end because a larger end would have already been seen or this one doesn’t extend coverage further than what’s tracked (though strictly speaking updating with max(max_end, end) handles both cases safely).
  4. Return: Return the final count.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N) due to sorting. The subsequent linear scan is O(N)O(N). Total time is dominated by sort.
  • Space Complexity: O(1)O(1) auxiliary space (ignoring input storage and Python’s internal stack for Timsort).

Solution

def removeCoveredIntervals(intervals):
    # Sort intervals: primary key start asc, secondary key end desc 
    # This ensures wider intervals starting at the same point come first.
    intervals.sort(key=lambda x: (x[0], -x[1]))
    
    count = 0
    max_end = float('-inf') 
    
    for _, end in intervals:
        if end > max_end:
            # This interval extends beyond any previously seen coverage boundary,
            # meaning it is not covered by previous intervals.
            count += 1
            max_end = end
    
    return count

# Example usage matching problem description logic (not required for submission)
# print(removeCoveredIntervals([[1,4],[3,6],[2,8]])) 

Edge Cases Handled

  • Single Interval: The loop runs once; end > -inf is true; returns 1. Correct.
  • All Covered by One Large Interval (e.g., [0,5], [1,4]): Sorted order places large interval first. First sets max_end. Second has smaller end ≤\le max. Count remains 1. Correct.
  • Same Start Times: Sorting with -x[1] ensures the largest range is processed first to establish a high coverage threshold for subsequent narrower intervals starting at that same point.
  • Disjoint Intervals (e.g., [0,2], [3,4]): Each interval has an end greater than previous max_end. Count increments every time. Correct.