只想到硬幹 O(N^2)
不過可以把每次pair檢查壓到O(1)
x從小排到大 同x的從大排到小
每次往比自己x大的檢查
每一輪固定A loopB時
隨時記下在A右下的點之中最上面的B
當你loop到的B點的y值比它小
代表它一定在你們中間
好饒口= =
def numberOfPairs(self, points: List[List[int]]) -> int:
points.sort(key=lambda p: (p[0], -p[1]))
rets = 0
n = len(points)
for i in range(n):
a_x, a_y = points[i][0], points[i][1]
cur_max_b_y = -1
for j in range(i+1, n):
b_x, b_y = points[j][0], points[j][1]
if b_y<=a_y:
if b_y>cur_max_b_y:
rets += 1
cur_max_b_y = max(cur_max_b_y, b_y)
return rets