[LeetCode] 3111. Minimum Rectangles to Cover Points

You are given a 2D integer array points, where points[i] = [xi, yi]. You are also given an integer w. Your task is to cover all the given points with rectangles.

Each rectangle has its lower end at some point (x1, 0) and its upper end at some point (x2, y2), where x1 <= x2, y2 >= 0, and the condition x2 - x1 <= w must be satisfied for each rectangle.

A point is considered covered by a rectangle if it lies within or on the boundary of the rectangle.

Return an integer denoting the minimum number of rectangles needed so that each point is covered by at least one rectangle.

Note: A point may be covered by more than one rectangle.

Example 1:

Input: points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
Output: 2

Explanation:
The image above shows one possible placement of rectangles to cover the points:
A rectangle with a lower end at (1, 0) and its upper end at (2, 8)
A rectangle with a lower end at (3, 0) and its upper end at (4, 8)

Example 2:

Input: points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
Output: 3

Explanation:
The image above shows one possible placement of rectangles to cover the points:
A rectangle with a lower end at (0, 0) and its upper end at (2, 2)
A rectangle with a lower end at (3, 0) and its upper end at (5, 5)
A rectangle with a lower end at (6, 0) and its upper end at (6, 6)

Example 3:

Input: points = [[2,3],[1,2]], w = 0
Output: 2

Explanation:
The image above shows one possible placement of rectangles to cover the points:
A rectangle with a lower end at (1, 0) and its upper end at (1, 2)
A rectangle with a lower end at (2, 0) and its upper end at (2, 3)

Constraints:
1 <= points.length <= 105
points[i].length == 2
0 <= xi == points[i][0] <= 109
0 <= yi == points[i][1] <= 109
0 <= w <= 109
All pairs (xi, yi) are distinct.

覆盖所有点的最少矩形数目。

给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。

每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都 必须 满足 x2 - x1 <= w 。

如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。

请你在确保每个点都 至少 被一个矩形覆盖的前提下，最少 需要多少个矩形。

注意：一个点可以被多个矩形覆盖。

思路

思路是对所有的点的横坐标排序。用矩形覆盖所有的点，因为不用考虑矩形的高度，所以只要考虑所有的点的横坐标即可。

排序过后我们来遍历所有的点的横坐标。如果挡板的左端点 + 宽度 w 够不到当前这个点的横坐标，则需要下一块板了；否则就遍历到下一个点，看挡板能否够得到下一个点。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, (a, b) -> a[0] - b[0]);
        int n = points.length;
		// 挡板的左边界
        int bound = points[0][0];
        int count = 1;
        int i = 1;
        while (i < n) {
			// 如果挡板的宽度够不到当前这个点的横坐标，则一定需要另一块板
            if (bound + w < points[i][0]) {
                count++;
                bound = points[i][0];
            } else {
                i++;
            }
        }
        return count;
    }
}