Leetcode 3027. Find the Number of Ways to Place People II

本文主要是介绍Leetcode 3027. Find the Number of Ways to Place People II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 3027. Find the Number of Ways to Place People II
- 1. 解题思路
- 2. 代码实现

题目链接：3027. Find the Number of Ways to Place People II

1. 解题思路

这一题的话我也没想到啥特别好的思路，采用的纯粹是遍历+剪枝的思路。

遍历的话好理解，对于 $N$ 个位置当中要找到任意两个位置作为Takina和Chisato的位置，一共就是 $O(N^2)$ 的算法复杂度，然后就是要判断这两个位置是否合法，这个至多又会引入 $O (N)$ 的算法复杂度，一共可能就变成了 $O(N^3)$ 的算法复杂度，明显太多了……

因此，我们就是在这里做了一下剪枝，首先的话，就是我们将坐标拍了个序，按照题意要求，两个点一个要在左上角，一个要在右下角，因此，我们将坐标按照 $(x, - y)$ 进行逆序排列，此时必然左上角的点会出现右下角的点的前方，且如果他们的区间当中有其他点的话，这个点只能出现在他们之间。

此时，我们发现提交的代码就能够通过所有测试样例了，感觉应该还能够优化，不过这里暂时就没往下深挖了，凑合着就算是做出来了吧，LOL

2. 代码实现

给出python代码实现如下：

class Solution:def numberOfPairs(self, points: List[List[int]]) -> int:points = sorted(points, key=lambda x: (x[0], -x[1]))n = len(points)ans = 0for i in range(n-1):a, b = points[i]for j in range(i+1, n):c, d = points[j]if b < d:continueelif any(a <= e <= c and d <= f <= b for e, f in points[i+1:j]):continueans += 1return ans