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
}

了卷別