각 점을 포함하는 직사각형의 수를 센다.

rectangles는 rectangles[i] = [li, hi] 직사각형의 길이가 ith이고 높이가 li임을 나타내는 2D 정수 배열 hi가 제공됩니다. 또한 2D 정수 배열points이 제공됩니다. 여기서 points[j] = [xj, yj]는 좌표가 (xj, yj)인 점입니다.
ith 직사각형은 좌표 (0, 0)에 왼쪽 아래 모서리 점이 있고 (li, hi)에 오른쪽 위 모서리 점이 있습니다.

길이가 count인 정수 배열points.length을 반환합니다. 여기서 count[j]는 jth 지점을 포함하는 사각형의 수입니다.
ith 사각형은 jth 및 0 <= xj <= li 인 경우 0 <= yj <= hi 점을 포함합니다. 사각형의 가장자리에 있는 점도 해당 사각형에 포함된 것으로 간주됩니다.

예 1:



입력: 사각형 = [[1,2],[2,3],[2,5]], 점 = [[2,1],[1,4]]
출력: [2,1]
설명:
첫 번째 직사각형에는 점이 없습니다.
두 번째 직사각형에는 점 (2, 1)만 포함됩니다.
세 번째 사각형에는 점 (2, 1)과 (1, 4)가 포함됩니다.
점 (2, 1)을 포함하는 사각형의 수는 2입니다.
점 (1, 4)를 포함하는 사각형의 수는 1입니다.
따라서 [2, 1]을 반환합니다.

예 2:



입력: 사각형 = [[1,1],[2,2],[3,3]], 점 = [[1,3],[1,1]]
출력: [1,3]
설명:
첫 번째 직사각형에는 점(1, 1)만 포함됩니다.
두 번째 사각형에는 점(1, 1)만 포함됩니다.
세 번째 사각형에는 점 (1, 3)과 (1, 1)이 포함됩니다.
점 (1, 3)을 포함하는 사각형의 수는 1입니다.
점 (1, 1)을 포함하는 사각형의 수는 3입니다.
따라서 [1, 3]을 반환합니다.

제약:

1 <= rectangles.length, points.length <= 5 * 104

rectangles[i].length == points[j].length == 2

1 <= li, xj <= 109

1 <= hi, yj <= 100

rectangles는 모두 고유합니다.

points는 모두 고유합니다.

해결책:

from collections import defaultdict
import bisect

class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        n = len(rectangles)
        heights = defaultdict(list)
        for l, h in rectangles:
            bisect.insort(heights[h], l)
        count = []
        for x, y in points:
            ctr = 0
            for h in range(y, 101):
                ctr += len(heights[h]) - bisect.bisect_left(heights[h], x)
            count.append(ctr)
        return count