What is the easiest approach to Find the Number of Ways to Place People I?

Iterate each point as an upper-left candidate and count all valid lower-right points using array filtering and inequality checks.

Can this problem be solved without sorting?

Yes, brute-force iteration works for n <= 50, but sorting can simplify comparisons and reduce mental errors.

What array plus math patterns are used here?

The key pattern is enumerating positions and applying coordinate inequalities to count valid geometric relationships.

How do I avoid counting duplicate pairs?

Ensure you always treat the first selected point as the upper-left and the second as lower-right, respecting strict inequalities.

Is there a faster approach for large n?

For larger n, segment trees or coordinate compression could reduce counting time, but for n <= 50, direct enumeration is efficient.

#3025

Medium

auto_awesome数组·数学

LeetCode 题解工作台

人员站位的方案数 I

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [x i , y i ] 。计算点对 (A, B) 的数量，其中 A 在 B 的左上角，并且它们形成的长方形中（或直线上）没有其它点（包括边界），除了点 A 和点 B 。返回数量。…

数组数学几何排序枚举

题目描述

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [x_i, y_i] 。

计算点对 (A, B) 的数量，其中

A 在 B 的左上角，并且
它们形成的长方形中（或直线上）没有其它点（包括边界），除了点 A 和点 B。

返回数量。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]

输出：0

解释：

没有办法选择 A 和 B，使得 A 在 B 的左上角。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]

输出：2

解释：

左边的是点对 (points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
中间的是点对 (points[2], points[1])，和左边的一样是合法的点对。
右边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]

输出：2

解释：

左边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
中间的是点对 (points[1], points[2])，和左边一样也是合法的点对。
右边的是点对 (points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。

提示：

2 <= n <= 50
points[i].length == 2
0 <= points[i][0], points[i][1] <= 50
points[i] 点对两两不同。

lightbulb

解题思路

方法一：排序 + 枚举

我们不妨考虑枚举矩形左上角的点 $(x_1, y_1)$ ，那么根据题目，右下角的点 $(x_2, y_2)$ 随着 $x$ 的增大，纵坐标 $y$ 也会要严格增大，才符合题意。

因此，我们对所有点按照 $x$ 坐标升序排序，如果 $x$ 坐标相同，按照 $y$ 坐标降序排序。

然后我们枚举左上角的点 $(x_1, y_1)$ ，并且维护一个最大的 $y_2$ ，记为 $maxY$ ，表示所有右下角的点的纵坐标的最大值。然后我们枚举右下角的点 $(x_2, y_2)$ ，如果 $y_2$ 大于 $maxY$ 并且小于等于 $y_1$ ，那么我们就找到了一个合法的方案，将答案加一，然后更新 $maxY$ 为 $y_2$ 。

枚举完所有的点对后，我们就得到了答案。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: (x[0], -x[1]))
        ans = 0
        for i, (_, y1) in enumerate(points):
            max_y = -inf
            for _, y2 in points[i + 1 :]:
                if max_y < y2 <= y1:
                    max_y = y2
                    ans += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) in the worst case due to double iteration over points, but acceptable for n <= 50. Space complexity is O(1) extra beyond input storage, unless using auxiliary arrays for sorting or counting.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to correct inequality directions for upper-left vs lower-right pairs.
question_mark
Consider how small constraints allow brute-force enumeration without performance penalty.
question_mark
Sorting points by x or y may simplify counting but is optional for correctness.

warning

常见陷阱

外企场景

error
Confusing upper-left with lower-left or upper-right positions when comparing coordinates.
error
Counting the same pair twice due to symmetric iteration over points.
error
Ignoring the strict inequality requirement in either x or y coordinates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count pairs with relaxed inequality, allowing A.x <= B.x and A.y >= B.y.
arrow_right_alt
Find all triples of points forming a specific geometric shape using similar enumeration.
arrow_right_alt
Extend to 3D coordinates, counting pairs where one point is strictly less in x and y but greater in z.

help

常见问题

外企场景

继续练习

#3027 人员站位的方案数 II #3380 用点构造面积最大的矩形 I #3102 最小化曼哈顿距离