Minimum Rectangles to Cover Points
Source: leetcode
Difficulty: Medium
Tags: array, greedy, sorting

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:**


![](https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-20-33-05.png)



**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:**


![](https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-18-59-12.png)



**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:**


![](https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-20-24-03.png)



**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.




C++ solution:
#pragma GCC optimize("O3", "unroll-loops")
class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        int n=points.size();
        vector<int> x(n,-1);
        for(int i=0; i<n; i++) x[i]=points[i][0];
        sort(x.begin(), x.end());
        int ans=0, k=0;
        while(k<n){
            k=upper_bound(x.begin()+k, x.end(), x[k]+w)-x.begin();
            ans++;
        } 
        return ans; 
    }
};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();

Go solution:
func minRectanglesToCoverPoints(points [][]int, w int) int {
    sort.Slice(points, func(i, j int) bool {
        return points[i][0] < points[j][0]
    })
    
    counter := 0
    n := len(points)
    x := points[0][0]
    index := 0
    for index != n {
        x += w
        counter++
        for index != n && points[index][0] <= x {
            index++
        }
        if index == n {
            break
        }
        x = points[index][0]
    }
    
    return counter
}

Java solution:
class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, (a,b) -> a[0]-b[0]);
        int count=0;
        for(int i=0;i<points.length;i++)
        {
            int j=i;
            while((j < points.length) && (points[j][0] - points[i][0] <= w) && (points[i][1] >= 0))
            {
                j++;
            }
            count++;
            i=j-1;
        }
        return count;
    }
}

JavaScript solution:
/**
 * @param {number[][]} points
 * @param {number} w
 * @return {number}
 */
var minRectanglesToCoverPoints = function(points, w) {
    points.sort((a, b) => a[0] - b[0]);
    let last = -Infinity, res = 0;
    for(let [x, y] of points) {
        if(x > last) {
            res++;
            last = x + w;
        }
    }

    return res;
};

Python solution:
class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        # only care about the x coordinates
        # sort it and then count?
        
        points.sort()
        start = points[0][0]
        count = 0

        for point in points:
            x = point[0]

            # print(point)
            # print(start, x)

            if x - start <= w:
                continue
            else:
                count+=1
                start = x

        return count + 1

Ruby solution:
# @param {Integer[][]} points
# @param {Integer} w
# @return {Integer}
def min_rectangles_to_cover_points(points, w)
    return 1 if points.length == 1

    x_cords = points.map {|p| p[0]}.sort
    sol = 1
    current = x_cords.shift

    x_cords.each do |x|
        next if x - current <= w
        
        sol += 1
        current = x
    end

    sol
end