Problem Statement in English

You’re given a list of intervals, where each interval is represented as a pair of integers [start, end]. An interval [a, b] is said to be covered by another interval [c, d] if and only if c <= a and b <= d.

Return the number of intervals that are not covered by any other interval in the list.

Approach

We can solve this problem by first sorting the intervals based on their end points in descending order. If two intervals have the same end point, we sort them by their start points in ascending order. This way, we can easily check if an interval is covered by the previous one.

If the current interval is covered by the previous one, we decrement the count of non-covered intervals. Otherwise, we update the previous interval to the current one.

And we’re done!

Solution in Python


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        N = len(intervals)
        if N == 1: return 1

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

        pStart, pEnd = intervals[0]
        res = N

        for start, end in intervals[1:]:
            if pStart <= start and end <= pEnd:
                res -= 1
            else:
                pStart = start
                pEnd = end

        return res

Complexity

  • Time: $O(N \log N)$
    Since we sort the intervals first, and then we iterate through the sorted list once, the overall time complexity is dominated by the sorting step, which is $O(N \log N)$.

  • Space: $O(1)$
    Since we are using a constant amount of extra space for variables, the space complexity is $O(1)$.

And we are done.