The Minimum Rectangles to Cover Points problem provides a list of 2D points and a fixed rectangle width W. You need to place axis-aligned rectangles of width W (and any height) to cover all points, minimizing the number of rectangles used. Rectangles can be placed anywhere, but each must cover points within a horizontal span of W. This Minimum Rectangles to Cover Points interview question is a greedy interval-covering problem.
Microsoft asks this to evaluate greedy strategy design for geometric coverage problems. The ability to simplify a 2D placement problem by focusing on one dimension (x-coordinates) while the other is unconstrained (y-coordinate) shows strong problem decomposition. The array, sorting, and greedy interview pattern applies elegantly here.
The key insight is that y-coordinates are irrelevant — since rectangles have unlimited height, a single rectangle can cover all points sharing a similar x-range. Sort all points by x-coordinate. Greedily place a rectangle starting at the leftmost uncovered point, extending it W units to the right, covering all points within [x, x + W]. Then move to the next uncovered point and repeat. Count total rectangles placed.
Points: [(1,2), (3,5), (6,1), (8,3), (10,4)], W = 4.
When a 2D geometry problem has unconstrained movement in one axis, always look to reduce it to a 1D problem. Sorting by the constrained dimension and applying a greedy sweep is a powerful pattern that appears in interval scheduling, painting, and coverage problems. Practice by solving interval covering and merging problems — they build the same intuition needed for Minimum Rectangles to Cover Points.
