Minimum rectangles to cover all points
Given a 2D array points[][], where points[i] = [xi, yi]. The task is to find the minimum number of rectangles of width `w` or less needed to cover all points in a given 2D array, where each rectangle’s lower end is at (x1, 0) and upper end at (x2, y2) with x1 = 0. A point is covered if it’s within or on the rectangle’s boundary. A point can be covered by multiple rectangles.
Examples:
Input: points[][] = {{2, 1}, {1, 0}, {1, 4}, {1, 8}, {3, 5}, {4, 6}}, w = 1
Output: 2
Explanation: 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)Input: points[][] = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}, w = 2
Output: 3
Explanation:
- A rectangle with a lower end at (0, 0) and its upper end at (2, 6)
- A rectangle with a lower end at (2, 0) and its upper end at (4, 6)
- A rectangle with a lower end at (4, 0) and its upper end at (6, 6)
Approach:
To solve this problem, we need to find the minimum number of rectangles that can cover all the given points with each rectangle’s width being w or less. The idea is to sort the points by their x coordinates and then use a greedy approach to cover as many points as possible with each rectangle. We can slide a window of width w along the x axis and count how many points are covered within each window.
Step-by-step algorithm:
- Sort the points array based on the x coordinate.
- Initialize a counter for the number of rectangles.
- Iterate through the sorted points and use a greedy approach to cover as many points as possible with each rectangle:
- Start a rectangle at the current point.
- Extend the rectangle’s width to cover the next w units along the x axis.
- Move to the next point that is not covered by the current rectangle.
- Continue until all points are covered.
- Return the count of rectangles used.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort points based on x coordinate
bool comparePoints(const vector<int>& a,
const vector<int>& b)
{
return a[0] < b[0];
}
int minRectangles(vector<vector<int> >& points, int w)
{
// Step 1: Sort points based on x coordinate
sort(points.begin(), points.end(), comparePoints);
int n = points.size();
int rectangles = 0;
int i = 0;
// Step 2: Iterate through points to cover them with
// rectangles
while (i < n) {
// Step 3: Define the current rectangle starting at
// the current point
int start = points[i][0];
rectangles++;
// Step 4: Move to the next point that is not
// covered by the current rectangle
while (i < n && points[i][0] <= start + w) {
i++;
}
}
return rectangles;
}
int main()
{
vector<vector<int> > points1
= { { 2, 1 }, { 1, 0 }, { 1, 4 },
{ 1, 8 }, { 3, 5 }, { 4, 6 } };
int w1 = 1;
cout << minRectangles(points1, w1) << endl; // Output: 2
return 0;
}
import java.util.*;
public class Main {
// Comparator function to sort points based on x
// coordinate
static class PointComparator
implements Comparator<int[]> {
public int compare(int[] a, int[] b)
{
return Integer.compare(a[0], b[0]);
}
}
public static int minRectangles(int[][] points, int w)
{
// Step 1: Sort points based on x coordinate
Arrays.sort(points, new PointComparator());
int n = points.length;
int rectangles = 0;
int i = 0;
// Step 2: Iterate through points to cover them with
// rectangles
while (i < n) {
// Step 3: Define the current rectangle starting
// at the current point
int start = points[i][0];
rectangles++;
// Step 4: Move to the next point that is not
// covered by the current rectangle
while (i < n && points[i][0] <= start + w) {
i++;
}
}
return rectangles;
}
public static void main(String[] args)
{
int[][] points1 = { { 2, 1 }, { 1, 0 }, { 1, 4 },
{ 1, 8 }, { 3, 5 }, { 4, 6 } };
int w1 = 1;
System.out.println(
minRectangles(points1, w1)); // Output: 2
}
}
// This code is contributed by Shivam
Output
2
Time Complexity: Sorting the points takes O(nlogn) time. The subsequent iteration through the points takes O(n) time. Therefore, the overall time complexity is O(nlogn).
Auxiliary Space: O(1) if we do not consider the input storage, as we are only using a few additional variables.