温州seo网站建设,重庆建设工程信息查询系统官网,as.net 网站开发视频教程,高科技公司网站模板2哥 : 3妹#xff0c;今天第一天上班啊#xff0c;开工大吉~ 3妹#xff1a;2哥#xff0c;开工大吉鸭#xff0c;有没有开工红包#xff1f; 2哥 : 我们公司比较扣#xff0c;估计不会发的。 3妹#xff1a;我们公司估计也一样#xff0c;不过依然挡不住我打工人的热…
2哥 : 3妹今天第一天上班啊开工大吉~ 3妹2哥开工大吉鸭有没有开工红包 2哥 : 我们公司比较扣估计不会发的。 3妹我们公司估计也一样不过依然挡不住我打工人的热情 2哥 :哈哈哈哈公司不给咱发红包咱们自掏腰包吃顿好的吧祝愿2024都发大财 3妹好鸭好鸭我想吃火锅红红火火 2哥没问题 3妹听说有的公司人员站成两排欢迎老板老板们给发红包 2哥好吧只要有红包站着舔老板也不是不可以说到人员站位今天有一道“人员站位”的题目 让我们先做一下吧~ 题目
给你一个 n x 2 的二维数组 points 它表示二维平面上的一些点坐标其中 points[i] [xi, yi] 。
我们定义 x 轴的正方向为 右 x 轴递增的方向x 轴的负方向为 左 x 轴递减的方向。类似的我们定义 y 轴的正方向为 上 y 轴递增的方向y 轴的负方向为 下 y 轴递减的方向。
你需要安排这 n 个人的站位这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处 恰好 有 一个 人。同时Alice 想跟 Bob 单独玩耍所以 Alice 会以 Bob 的坐标为 左上角 Bob 的坐标为 右下角 建立一个矩形的围栏注意围栏可能 不 包含任何区域也就是说围栏可能是一条线段。如果围栏的 内部 或者 边缘 上有任何其他人Alice 都会难过。
请你在确保 Alice 不会 难过的前提下返回 Alice 和 Bob 可以选择的 点对 数目。
注意Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角Bob 的位置是矩形的右下角。比方说以 (1, 1) (1, 3) (3, 1) 和 (3, 3) 为矩形的四个角给定下图的两个输入Alice 都不能建立围栏原因如下
图一中Alice 在 (3, 3) 且 Bob 在 (1, 1) Alice 的位置不是左上角且 Bob 的位置不是右下角。 图二中Alice 在 (1, 3) 且 Bob 在 (1, 1) Bob 的位置不是在围栏的右下角。
示例 1 输入points [[1,1],[2,2],[3,3]] 输出0 解释没有办法可以让 Alice 的围栏以 Alice 的位置为左上角且 Bob 的位置为右下角。所以我们返回 0 。
示例 2 输入points [[6,2],[4,4],[2,6]] 输出2 解释总共有 2 种方案安排 Alice 和 Bob 的位置使得 Alice 不会难过
Alice 站在 (4, 4) Bob 站在 (6, 2) 。Alice 站在 (2, 6) Bob 站在 (4, 4) 。 不能安排 Alice 站在 (2, 6) 且 Bob 站在 (6, 2) 因为站在 (4, 4) 的人处于围栏内。 示例 3 输入points [[3,1],[1,3],[1,1]] 输出2 解释总共有 2 种方案安排 Alice 和 Bob 的位置使得 Alice 不会难过Alice 站在 (1, 1) Bob 站在 (3, 1) 。Alice 站在 (1, 3) Bob 站在 (1, 1) 。 不能安排 Alice 站在 (1, 3) 且 Bob 站在 (3, 1) 因为站在 (1, 1) 的人处于围栏内。 注意围栏是可以不包含任何面积的上图中第一和第二个围栏都是合法的。
提示
2 n 1000 points[i].length 2 -10^9 points[i][0], points[i][1] 10^9 points[i] 点对两两不同。
思路 将 points 按照横坐标从小到大排序横坐标相同的按照纵坐标从大到小排序。
如此一来在枚举 points[i] 和 points[j]时ij就只需要关心纵坐标的大小。
固定 points[i]然后枚举 points[j]
如果 points[j][1] 比之前枚举的点的纵坐标都大那么矩形内没有其它点符合要求答案加一。 如果 points[j][1]小于等于之前枚举的某个点的纵坐标那么矩形内有其它点不符合要求。 所以在枚举 points[j]的同时需要维护纵坐标的最大值 maxY。这也解释了为什么横坐标相同的按照纵坐标从大到小排序。这保证了横坐标相同时我们总是优先枚举更靠上的点不会误把包含其它点的矩形也当作符合要求的矩形。
java代码
class Solution {public int numberOfPairs(int[][] points) {Arrays.sort(points, (p, q) - p[0] ! q[0] ? p[0] - q[0] : q[1] - p[1]);int ans 0;for (int i 0; i points.length; i) {int y0 points[i][1];int maxY Integer.MIN_VALUE;for (int j i 1; j points.length; j) {int y points[j][1];if (y y0 y maxY) {maxY y;ans;}}}return ans;}
}
