【数学】【排序】【C++算法】3027人员站位的方案数

本文涉及知识点

数学 排序

LeetCoce3027人员站位的方案数

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

我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。

你需要安排这 n 个人的站位，这 n 个人中包括 liupengsay 和小羊肖恩 。你需要确保每个点处 恰好 有 一个 人。同时，liupengsay 想跟小羊肖恩单独玩耍，所以 liupengsay 会以 liupengsay 的坐标为 左上角 ，小羊肖恩的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。如果围栏的 内部 或者 边缘 上有任何其他人，liupengsay 都会难过。

请你在确保 liupengsay 不会 难过的前提下，返回 liupengsay 和小羊肖恩可以选择的 点对 数目。

注意，liupengsay 建立的围栏必须确保 liupengsay 的位置是矩形的左上角，小羊肖恩的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，liupengsay 都不能建立围栏，原因如下：

liupengsay 在 (3, 3) 且小羊肖恩在 (1, 1) ，liupengsay 的位置不是左上角且小羊肖恩的位置不是右下角。

，liupengsay 在 (1, 3) 且小羊肖恩在 (1, 1) ，小羊肖恩的位置不是在围栏的右下角。

示例 1：

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

输出：0

解释：没有办法可以让 liupengsay 的围栏以 liupengsay 的位置为左上角且小羊肖恩的位置为右下角。所以我们返回 0 。

示例 2：

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

输出：2

解释：总共有 2 种方案安排 liupengsay 和小羊肖恩的位置，使得 liupengsay 不会难过：

• liupengsay 站在 (4, 4) ，小羊肖恩站在 (6, 2) 。
• liupengsay 站在 (2, 6) ，小羊肖恩站在 (4, 4) 。
  不能安排 liupengsay 站在 (2, 6) 且小羊肖恩站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。
  示例 3：
  

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

输出：2

解释：总共有 2 种方案安排 liupengsay 和小羊肖恩的位置，使得 liupengsay 不会难过：

• liupengsay 站在 (1, 1) ，小羊肖恩站在 (3, 1) 。
• liupengsay 站在 (1, 3) ，小羊肖恩站在 (1, 1) 。
  不能安排 liupengsay 站在 (1, 3) 且小羊肖恩站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。
  注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。

提示：

2 <= n <= 1000

points[i].length == 2

-10⁹ <= points[i][0], points[i][1] <= 10⁹

points[i] 点对两两不同。

数学

liupengsay 在左上，羊在右下。且没有人在 liupengsay右下，同时羊在此人右下。

右下有两种情况：

x等于,y小于。

x大于,y小于或等于。

对位置排序：x小的在前面，x相等则y大的在前。   ⟺    \iff⟺ 如果points[j]是points[i]的右下在i<j。

枚举：i 和j

1，由于已经排序，所以points[i].x <= pints[j].x。

2，判断points[i].y是否小于等于points[j].y。

3，判断是否有人处于：liupengsay和羊h之间。

a,i，j之间的人k ，x一定处于两者之间。

b,只需要记录y小于等于 liupengsa的最大y，如果此人不在羊的上边，则其他更不会在羊的上边。

代码

核心代码

class Solution {
public:
  int numberOfPairs(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [&](auto& v1, auto& v2) {return (v1[0] < v2[0]) || ((v1[0] == v2[0]) && (v1[1] > v2[1])); });
    int iRet = 0;
    for (int i = 0; i < points.size(); i++)
    {
      int iMax = INT_MIN;
      for (int j = i + 1; j < points.size(); j++)
      {
        if (points[j][1] <= points[i][1])
        {
          if (points[j][1] > iMax)
          {
            iRet++;
          }
          iMax = max(iMax, points[j][1]);
        }
      }
    }
    return iRet;
  }
};

旧版代码

class Solution {
public:
int numberOfPairs(vector<vector>& points) {
sort(points.begin(), points.end(), [](auto& v1, auto& v2) {return (v1[0] < v2[0])||((v1[0] == v2[0])&& (v1[1] > v2[1])); });
int iRet = 0;
for (int i = 0; i < points.size(); i++)
{
set setY;
for (int j = i+1; j < points.size(); j++)
{
if (points[j][1] <= points[i][1])
{
if (setY.empty() || (*setY.begin()< points[j][1]))
{
iRet++;
}
setY.insert(points[j][1]);
if (setY.size() > 1)
{
setY.erase(setY.begin());
}
}
}
}
return iRet;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。