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 = 0
        for i in range(n-1):
            a, b = points[i]
            for j in range(i+1, n):
                c, d = points[j]
                if b < d:
                    continue
                elif any(a <= e <= c and d <= f <= b for e, f in points[i+1:j]):
                    continue
                ans += 1
        return ans

提交代码评测得到：耗时6105ms，占用内存17MB。