东莞做微网站,制作静态网站制作,专业网站建设策划,八爪鱼磁力搜索引擎题目#xff1a;
给你一个二维整数数组 point #xff0c;其中 points[i] [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。
每个矩形的左下角在某个点 (x1, 0) 处#xff0c;且右上角在某个点 (x2, y2) 处#xff0c;其中 x1 x…题目
给你一个二维整数数组 point 其中 points[i] [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。
每个矩形的左下角在某个点 (x1, 0) 处且右上角在某个点 (x2, y2) 处其中 x1 x2 且 y2 0 同时对于每个矩形都 必须 满足 x2 - x1 w 。
如果一个点在矩形内或者在边上我们说这个点被矩形覆盖了。
请你在确保每个点都 至少 被一个矩形覆盖的前提下最少 需要多少个矩形。
注意一个点可以被多个矩形覆盖。
示例 1 输入points [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w 1 输出2 解释 上图展示了一种可行的矩形放置方案 一个矩形的左下角在 (1, 0) 右上角在 (2, 8) 。 一个矩形的左下角在 (3, 0) 右上角在 (4, 8) 。
示例 2 输入points [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w 2 输出3 解释 上图展示了一种可行的矩形放置方案 一个矩形的左下角在 (0, 0) 右上角在 (2, 2) 。 一个矩形的左下角在 (3, 0) 右上角在 (5, 5) 。 一个矩形的左下角在 (6, 0) 右上角在 (6, 6) 。
示例 3 输入points [[2,3],[1,2]], w 0 输出2 解释 上图展示了一种可行的矩形放置方案 一个矩形的左下角在 (1, 0) 右上角在 (1, 2) 。 一个矩形的左下角在 (2, 0) 右上角在 (2, 3) 。
提示 1 points.length 105 points[i].length2 0 xi points[i][0] 109 0 yi points[i][1] 109 0 w 109 所有点坐标 (xi, yi) 互不相同。
思路
贪心按横坐标从小打到排序查看需要多少次能将横坐标全部覆盖每次和xw进行比较xw内代表都可覆盖超过此范围的则代表需要一个新矩形。
代码
class Solution {//贪心 横坐标需要几个矩形可以覆盖public int minRectanglesToCoverPoints(int[][] points, int w) {// 按横坐标从小到大排序Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));int ans 0;// 每次用xw来更新边界值int bound -1;for (int[] p : points) {if (p[0] bound) {bound p[0] w;ans;}}return ans;}
}
