通过万岁!!!
- 题目:这个题目中虽然给了一个二维数组,但是其实我们可以理解为一维数组。因为y坐标根本用不到。题目的意思就是在一维坐标轴上有n个点,然后有ret个长度最大为w的线段,然后问你怎么样才能让这n个点都在这ret个w的线段上。
- 思路:看到这个题目,我们肯定让线段的长度最大,也就是w,思想就是贪心。对n个点进行排序,然后定义一个变量right,表示当前线段的右侧坐标的值,初始值应该是第一个点+w。然后便利n个点,如果当前点小于right,也就说明之前的线段无法覆盖当前点。那么right就应该等于当前点+w了,也就是来一个新的线段,那么线段数量肯定是要+1的
- 技巧:贪心、排序
java代码
class Solution {public int minRectanglesToCoverPoints(int[][] points, int w) {int ret = 1;Arrays.sort(points, Comparator.comparingInt(o -> o[0]));int right = points[0][0] + w;for (int[] point : points) {if (right < point[0]) {right = point[0] + w;ret++;}}return ret;}
}
- 总结:题目其实不难,可能比较陌生的地方就是针对二维数组如何对第一列进行排序。