题目：

给你一个二维整数数组 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].length == 2
• 0 <= xi == points[i][0] <= 109
• 0 <= yi == points[i][1] <= 109
• 0 <= w <= 109
• 所有点坐标 (xi, yi) 互不相同。

思路：

从题目给的案例，一步一步分析

要拿矩形覆盖点，由于矩形的纵向高度没有要求，横向最多 w，要求最少的矩形数，所以每个用于覆盖的矩形肯定是（w, + 无穷） 大矩形不用白不用嘛

从这里看来，我们就只需要考虑点的横坐标就好了。那么从最左边的点开始一个个去覆盖，看用矩形一次能覆盖多少个点。

枚举点的横坐标，用矩形覆盖（会同时覆盖后面几个点），这样枚举完所有点，就能求最少覆盖矩形

代码：

class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        // 由于矩形的高度是不受限制的，所以我们只需要考虑横坐标
        // 对于覆盖类题目（看着混乱的），必须捋顺起始点，这样才有抓手开始
        int n = points.size();
        vector<int> position(n);
        for (int i = 0; i < n; i++) {
            position[i] = points[i][0];
        }
        sort(position.begin(), position.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int start = position[i];
            int j = i + 1;
            while (j < n && position[j] <= start + w) {
                j++;
            }
            i = j - 1;
            ans++;
        }
        return ans;
    }
};