Medium

题目描述

给你一个二维整数数组 points，其中 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

示例 2：

输入：points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出：3

示例 3：

输入：points = [[2,3],[1,2]], w = 0
输出：2

约束条件：

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • 0 <= xi == points[i][0] <= 10^9
  • 0 <= yi == points[i][1] <= 10^9
  • 0 <= w <= 10^9
  • 所有的 (xi, yi) 都是不同的

解题思路

这是一个典型的贪心算法问题。关键观察是：

  1. y坐标无关性：矩形的高度可以任意调整（从0到最大y值），因此y坐标不影响矩形的数量，只有x坐标是关键因素。

  2. 贪心策略：将所有点按x坐标排序后，使用贪心算法：

    • 选择最左边未覆盖的点作为当前矩形的起点
    • 尽可能向右扩展矩形，覆盖所有在宽度w范围内的点
    • 重复这个过程直到所有点都被覆盖

  3. 算法流程：

    • 提取所有不重复的x坐标并排序
    • 从最小的x坐标开始，每次选择一个矩形的左端点
    • 该矩形可以覆盖从当前x到x+w范围内的所有点
    • 跳过已覆盖的点，继续处理下一个未覆盖的x坐标

这种贪心策略是最优的，因为每个矩形都尽可能覆盖更多的点，不会造成浪费。

代码实现

class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        vector<int> xCoords;
        for (const auto& point : points) {
            xCoords.push_back(point[0]);
        }
        
        sort(xCoords.begin(), xCoords.end());
        xCoords.erase(unique(xCoords.begin(), xCoords.end()), xCoords.end());
        
        int rectangles = 0;
        int i = 0;
        
        while (i < xCoords.size()) {
            int start = xCoords[i];
            rectangles++;
            
            while (i < xCoords.size() && xCoords[i] <= start + w) {
                i++;
            }
        }
        
        return rectangles;
    }
};

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        x_coords = sorted(set(point[0] for point in points))
        
        rectangles = 0
        i = 0
        
        while i < len(x_coords):
            start = x_coords[i]
            rectangles += 1
            
            while i < len(x_coords) and x_coords[i] <= start + w:
                i += 1
        
        return rectangles

public class Solution {
    public int MinRectanglesToCoverPoints(int[][] points, int w) {
        var xCoords = points.Select(p => p[0]).Distinct().OrderBy(x => x).ToList();
        
        int rectangles = 0;
        int i = 0;
        
        while (i < xCoords.Count) {
            int start = xCoords[i];
            rectangles++;
            
            while (i < xCoords.Count && xCoords[i] <= start + w) {
                i++;
            }
        }
        
        return rectangles;
    }
}

var minRectanglesToCoverPoints = function(points, w) {
    const xCoords = [...new Set(points.map(point => point[0]))].sort((a, b) => a - b);
    
    let rectangles = 0;
    let i = 0;
    
    while (i < xCoords.length) {
        const start = xCoords[i];
        rectangles++;
        
        while (i < xCoords.length && xCoords[i] <= start + w) {
            i++;
        }
    }
    
    return rectangles;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是点的数量。时间复杂度主要来自排序操作，空间复杂度来自存储去重后的x坐标。

相关题目