Remove Covered Intervals – Python Solution

Problem Description

The “Remove Covered Intervals” problem is akin to finding the best seat in a crowded movie theater, only to discover that someone has already claimed your desired spot in a way that obstructs your view. Given a list of intervals, your task is to determine how many of those intervals are not covered by others.

Imagine you’re at a party where everyone is trying to outshine each other with their dance moves. Some individuals perform the same moves but with a bit more flair. Your job is to count how many unique dance moves are actually being showcased. If someone is doing the same move but for a longer duration, they are merely showing off, and you can disregard them!

Code Solution


class Solution:
    def removeCoveredIntervals(self, intervals: list[list[int]]) -> int:
        ans = 0
        prevEnd = 0

        # If the two intervals have the same `start`, put the one with a larger
        # `end` first.
        for _, end in sorted(intervals, key=lambda x: (x[0], -x[1])):
            # Current interval is not covered by the previous one.
            if prevEnd < end:
                ans += 1
                prevEnd = end

        return ans

Approach

The approach taken in this solution is quite elegant. First, we sort the intervals based on their starting points. If two intervals have the same starting point, we sort them by their ending points in descending order. This way, we can easily identify which intervals are covered by others.

We then iterate through the sorted intervals, keeping track of the end of the last interval that was counted as not covered. If the current interval's end is greater than the last counted end, it means it’s not covered, and we increment our count.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(1)

Real-World Example

Imagine you are organizing a series of events in a community center. Each event has a start and end time. Some events overlap, and you want to know how many unique events you can actually host without any overlap. By applying the "Remove Covered Intervals" logic, you can easily determine which events can coexist without stepping on each other's toes!