Choose the fewest fixed-width rectangles to cover all points on a 2D plane, where each rectangle spans the full vertical range and has a limited width on the x-axis.
Given a list of 2D points and an integer width , place axis-aligned rectangles so that every point is covered by at least one rectangle.
Each rectangle has:
- width exactly on the x-axis
- unlimited height on the y-axis
- sides parallel to the axes
A point is covered if its x-coordinate lies within a rectangle's horizontal span. Since the rectangle extends infinitely in the y-direction for this problem formulation, only the x-coordinate matters.
Return the minimum number of rectangles needed to cover all points.
Input Format
- An array of points, where each point is represented as
[x, y]. - An integer
w, the rectangle width.
You may assume the rectangles can be placed anywhere on the x-axis.
Output Format
- Return a single integer: the minimum number of rectangles required to cover every point.
Constraints
- Points may share the same x-coordinate.
- and coordinates are integers.
- The answer should be computed efficiently for large inputs.
Example 1
Input
points = [[2,1],[3,3],[6,2],[8,4]], w = 2
Output
2
Explanation
One rectangle can cover x-values from 2 to 4, covering points with x = 2 and 3. Another can cover x-values from 6 to 8, covering the remaining two points.
Example 2
Input
points = [[1,5],[2,7],[4,1]], w = 3
Output
1
Explanation
A single rectangle covering x-values from 1 to 4 is enough to cover all points.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.