LeetCode 3111 覆盖所有点的最少矩形数目
方法1:贪心
class Solution:
def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
lst = sorted(set(x for x, _ in points))
ans, idx, i = 1, 0, 0 # 位于第一个
while i < len(lst):
if lst[i] - lst[idx] > w:
ans += 1; idx = i
i += 1
return ans
class Solution {
public int minRectanglesToCoverPoints(int[][] points, int w) {
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int ans = 0, high = -1; // 最高值
for(int[] info : points) {
if(info[0] > high) {
high = info[0] + w; // 更新最高值
ans++;
}
}
return ans;
}
}
标签:info,high,int,31,2024,lst,points,ans,每日
From: https://www.cnblogs.com/XuGui/p/18334252