只想到硬干 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