Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


![](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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


![](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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


![](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 <= 10^5
  • points[i].length == 2
  • 0 <= xi == points[i][0] <= 10^9
  • 0 <= yi == points[i][1] <= 10^9
  • 0 <= w <= 10^9
  • All pairs (xi, yi) are distinct.

Solution

Method 1 – Greedy Interval Covering

Intuition

Since rectangles can cover any y, we only need to cover all x-coordinates with intervals of width ≤ w. Sort points by x, and greedily cover as many as possible with each rectangle.

Approach

  1. Sort points by x.
  2. Start from the leftmost point, cover all points with x in [x0, x0+w] with one rectangle.
  3. Move to the next uncovered point and repeat.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
#include <algorithm>
class Solution {
public:
    int minRectanglesToCoverPoints(std::vector<std::vector<int>>& points, int w) {
        std::sort(points.begin(), points.end());
        int n = points.size(), ans = 0, i = 0;
        while (i < n) {
            int x0 = points[i][0];
            while (i < n && points[i][0] <= x0 + w) i++;
            ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import "sort"
func minRectanglesToCoverPoints(points [][]int, w int) int {
    sort.Slice(points, func(i,j int) bool { return points[i][0]<points[j][0] })
    n, ans, i := len(points), 0, 0
    for i < n {
        x0 := points[i][0]
        for i < n && points[i][0] <= x0+w { i++ }
        ans++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, Comparator.comparingInt(a->a[0]));
        int n = points.length, ans = 0, i = 0;
        while (i < n) {
            int x0 = points[i][0];
            while (i < n && points[i][0] <= x0+w) i++;
            ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minRectanglesToCoverPoints(points: Array<IntArray>, w: Int): Int {
        points.sortBy{it[0]}
        var ans = 0; var i = 0; val n = points.size
        while (i < n) {
            val x0 = points[i][0]
            while (i < n && points[i][0] <= x0+w) i++
            ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minRectanglesToCoverPoints(self, points: list[list[int]], w: int) -> int:
        points.sort()
        n, ans, i = len(points), 0, 0
        while i < n:
            x0 = points[i][0]
            while i < n and points[i][0] <= x0+w:
                i += 1
            ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn min_rectangles_to_cover_points(mut points: Vec<Vec<i32>>, w: i32) -> i32 {
        points.sort();
        let n = points.len();
        let mut ans = 0; let mut i = 0;
        while i < n {
            let x0 = points[i][0];
            while i < n && points[i][0] <= x0+w { i += 1; }
            ans += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minRectanglesToCoverPoints(points: number[][], w: number): number {
        points.sort((a,b)=>a[0]-b[0]);
        let n = points.length, ans = 0, i = 0;
        while (i < n) {
            let x0 = points[i][0];
            while (i < n && points[i][0] <= x0+w) i++;
            ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — Sort points, then one pass.
  • 🧺 Space complexity: O(1) — In-place sort.