3025. Find the Number of Ways to Place People I
思路:
按照x由小到大排序points
如果x一样大就将y较大的排在前面
接着开始检查所有pair
默认points[i]是左上点, 从j=i+1开始检查右下点
因为排序过的关系, 所以points[j]一定比points[i]还要右边
那就只要检查y, 令top = points[i][1]
令bottom为前一个能构成pair的points[j][1]
points[j][1]不能超过top, 也不能小于bottom
这样就能得到答案了
golang :
func numberOfPairs(points [][]int) int {
slices.SortFunc(points, func(i, j []int) int {
if i[0] == j[0] {
return j[1] - i[1]
}
return i[0] - j[0]
})
n, ans := len(points), 0
for i := 0; i < n; i++ {
top := points[i][1]
bottom := math.MinInt64
for j := i + 1; j < n; j++ {
if points[j][1] <= top && points[j][1] > bottom {
ans++
bottom =points[j][1]
if points[j][1] == top{
break
}
}
}
}
return ans
}

了卷别