Problem Description

You are given an array of intervals where each interval is represented as [li, ri), meaning it starts at li (inclusive) and ends at ri (exclusive). Your task is to remove all intervals that are completely covered by another interval in the list.

An interval [a, b) is considered covered by interval [c, d) if and only if c <= a and b <= d. In other words, the covering interval must start at or before the covered interval's start point AND end at or after the covered interval's end point.

After removing all covered intervals, return the count of intervals that remain.

For example:

• Interval [1, 4) is covered by [0, 5) because 0 ≤ 1 and 4 ≤ 5
• Interval [2, 6) is NOT covered by [1, 4) because 6 > 4

The solution works by sorting intervals first by start point (ascending), then by end point (descending) when start points are equal. This ordering ensures that when we encounter an interval with the same start point, we see the one with the larger range first. As we traverse the sorted list, we only count intervals whose end points extend beyond the maximum end point seen so far, as these cannot be covered by any previous interval.

Intuition

The key insight is that if we want to identify which intervals are not covered by others, we need a systematic way to compare them. Consider what makes an interval covered: it needs another interval that starts at or before it AND ends at or after it.

If we sort intervals by their starting points, we can process them in order and know that any interval that could potentially cover the current one must either come before it (same or earlier start) or after it (later start). But intervals with later starts can never cover earlier ones, so we only need to look at what came before.

However, when two intervals have the same starting point, which one should we process first? If interval A is [1, 3) and interval B is [1, 5), then B covers A. By processing B first (the one with the larger endpoint when starts are equal), we can track that we've seen an interval extending to 5. When we later see A, we know it's covered because its endpoint 3 doesn't extend beyond 5.

This leads to the sorting strategy: (x[0], -x[1]) - sort by start ascending, but by end descending when starts are equal. The negative sign ensures larger endpoints come first when starts are tied.

As we traverse the sorted intervals, we maintain the maximum endpoint seen so far. If the current interval's endpoint exceeds this maximum, it cannot be covered by any previous interval (since all previous intervals either started before or at the same point, and none extended far enough). These are the intervals we count.

The elegance of this approach is that it reduces a potentially complex comparison problem (checking every pair of intervals) to a simple linear scan with a single variable tracking the "coverage boundary."

Learn more about Sorting patterns.

Solution Approach

The implementation follows a greedy approach with sorting to efficiently identify non-covered intervals:

Step 1: Sort the intervals

intervals.sort(key=lambda x: (x[0], -x[1]))

We sort the intervals using a custom key that:

• Sorts by the left endpoint x[0] in ascending order
• When left endpoints are equal, sorts by the right endpoint -x[1] in descending order (negative sign reverses the order)

This sorting ensures that for intervals with the same starting point, we process the one with the larger range first.

Step 2: Initialize tracking variables

ans = 0
pre = -inf

• ans counts the number of non-covered intervals
• pre tracks the maximum right endpoint seen so far, initialized to negative infinity to ensure the first interval is always counted

Step 3: Traverse and count non-covered intervals

for _, cur in intervals:
    if cur > pre:
        ans += 1
        pre = cur

For each interval in the sorted list:

• We only care about the right endpoint cur (the left endpoint is handled by sorting)
• If cur > pre, the current interval extends beyond all previous intervals, meaning it cannot be covered by any of them
• When we find such an interval, we increment our count and update pre to this new maximum right endpoint

The algorithm works because:

1. Due to sorting, any interval that could cover the current one must appear before it
2. An interval is covered only if its right endpoint doesn't exceed the maximum right endpoint seen so far
3. By tracking only the maximum right endpoint (pre), we efficiently determine coverage without comparing every pair

Time Complexity: O(n log n) for sorting, where n is the number of intervals
Space Complexity: O(1) if we don't count the sorting space

Example Walkthrough

Let's walk through the solution with intervals: [[1,4], [3,6], [2,8], [1,2]]

Step 1: Initial Setup

• Input intervals: [[1,4], [3,6], [2,8], [1,2]]
• We need to find how many intervals are NOT covered by others

Step 2: Sort the intervals Using the sorting key (x[0], -x[1]):

• [1,4] → key: (1, -4)
• [3,6] → key: (3, -6)
• [2,8] → key: (2, -8)
• [1,2] → key: (1, -2)

After sorting:

1. [1,4] (key: (1, -4))
2. [1,2] (key: (1, -2))
3. [2,8] (key: (2, -8))
4. [3,6] (key: (3, -6))

Notice how [1,4] comes before [1,2] because when starts are equal (both 1), we sort by larger endpoint first (-4 < -2).

Step 3: Traverse and count Initialize: ans = 0, pre = -inf

1. Process [1,4]:

   • Right endpoint: 4
   • Is 4 > -inf? Yes
   • This interval is not covered → ans = 1
   • Update pre = 4

2. Process [1,2]:

   • Right endpoint: 2
   • Is 2 > 4? No
   • This interval IS covered by [1,4] → ans stays 1
   • pre remains 4

3. Process [2,8]:

   • Right endpoint: 8
   • Is 8 > 4? Yes
   • This interval is not covered → ans = 2
   • Update pre = 8

4. Process [3,6]:

   • Right endpoint: 6
   • Is 6 > 8? No
   • This interval IS covered by [2,8] → ans stays 2
   • pre remains 8

Result: 2 intervals remain ([1,4] and [2,8])

Verification:

• [1,2] is covered by [1,4] (1 ≤ 1 and 2 ≤ 4) ✓
• [3,6] is covered by [2,8] (2 ≤ 3 and 6 ≤ 8) ✓
• [1,4] is not covered by any interval
• [2,8] is not covered by any interval

The algorithm correctly identifies the 2 non-covered intervals.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of intervals. This is dominated by the sorting operation intervals.sort(key=lambda x: (x[0], -x[1])), which uses Python's Timsort algorithm with O(n × log n) complexity. After sorting, the code iterates through the intervals once with a simple loop, which takes O(n) time. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

The space complexity is O(log n). While the input list is sorted in-place (not creating a new list), Python's Timsort algorithm requires O(log n) space for its recursive call stack during the sorting process. The remaining variables (ans, pre, cur) use only O(1) additional space. Therefore, the total space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Sorting Logic

Pitfall: Using regular ascending sort for both start and end points intervals.sort() or intervals.sort(key=lambda x: (x[0], x[1])). This causes intervals with the same start point to be processed in ascending order of their end points, meaning shorter intervals are processed first.

Why it's wrong: When shorter intervals come first, they get counted as non-covered, but they're actually covered by the longer intervals that come later.

Example where it fails:

intervals = [[1, 4], [1, 6], [1, 8]]
# Wrong sort: [[1, 4], [1, 6], [1, 8]]
# Would incorrectly count all 3 as non-covered
# Correct sort: [[1, 8], [1, 6], [1, 4]]
# Correctly counts only 1 as non-covered

Solution: Always use intervals.sort(key=lambda x: (x[0], -x[1])) to ensure longer intervals with the same start point are processed first.

2. Using Wrong Comparison for Coverage Check

Pitfall: Checking if cur >= pre: instead of if cur > pre:. The equality case is crucial here.

Why it's wrong: If an interval ends exactly where the maximum end point is, it's still covered (e.g., [1, 4] is covered by [0, 4]).

Example where it fails:

intervals = [[0, 4], [1, 4], [2, 3]]
# With >= comparison: would count [1, 4] as non-covered
# With > comparison: correctly identifies [1, 4] as covered

Solution: Use strict inequality if cur > pre: to ensure intervals ending at the same point as a previous interval are considered covered.

3. Forgetting Edge Cases with Negative Numbers

Pitfall: Initializing pre to 0 instead of negative infinity, assuming all intervals have non-negative coordinates.

Why it's wrong: If intervals can have negative coordinates, initializing to 0 might incorrectly skip counting valid intervals.

Example where it fails:

intervals = [[-10, -5], [-8, -3]]
# With pre = 0: would skip both intervals
# With pre = -inf: correctly counts both intervals

Solution: Always initialize pre = -math.inf or use a sufficiently small value like float('-inf') to handle all possible interval ranges.