BinarySearch 0893 Count Contained Intervals

Problem statement

https://binarysearch.com/problems/Count-Contained-Intervals/

Solution

Similar to BinarySearch 0811 Remove Smaller Coordinates, but now we need to consider pairs (-x, y).

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, P):
        arr = sorted(((-x, y) for (x, y) in P), key=lambda x: (-x[0], -x[1]))
        ans, last_y = 0, -float("inf")
        for x, y in arr:
            if y > last_y:
                ans += 1
                last_y = y
        return len(P) - ans