Java || Greedy
Intuition:\n\nThe goal is to find the minimum number of vertical rectangles, each of width w, needed to cover all given points on a 2D plane. The key observatio
# Intuition:\n\nThe goal is to find the minimum number of vertical rectangles, each of width `w`, needed to cover all given points on a 2D plane. The key observation is that we only need to consider the x-coordinates of the points because the width of each rectangle is fixed and vertical, so the y-coordinates don\'t affect the coverage along the x-axis.\n\n# Approach:\n\n1. **Extract X-coordinates:** Extract the x-coordinates of all points and store them in an array `x`.\n2. **Sort the X-coordinates:** Sort the array `x` to process the points in increasing order.\n3. **Cover Points with Rectangles:**\n   - Initialize a counter `count` to keep track of the number of rectangles used.\n   - Iterate through the sorted x-coordinates.\n   - For each starting point, determine the furthest point that can be covered within the width `w`.\n   - Move the starting point to the next uncovered point and increment the rectangle counter.\n\n# Time Complexity:\n\n- **Extracting X-coordinates:** This takes \\(O(n)\\) time, where \\(n\\) is the number of points.\n- **Sorting X-coordinates:** Sorting takes \\(O(n \\log n)\\) time.\n- **Covering Points:** This step involves a linear scan through the sorted array, taking \\(O(n)\\) time.\n\nThus, the overall time complexity is \\(O(n \\log n)\\), dominated by the sorting step.\n\n# Space Complexity:\n\n- **Auxiliary Array:** An auxiliary array `x` of size \\(n\\) is used to store the x-coordinates.\n- **Sorting:** The sorting algorithm typically uses \\(O(n)\\) additional space for the sorting process (depending on the implementation).\n\nThus, the space complexity is \\(O(n)\\).\n\n\n# Code\n```\nclass Solution {\n    public int minRectanglesToCoverPoints(int[][] points, int w) {\n        int[] x = new int[points.length];\n        for(int i = 0;i<points.length;i++){\n            x[i]= points[i][0];\n        }\n        Arrays.sort(x);\n        int in = 0;\n        int count = 0;\n        while(in<x.length){\n            int j = in;\n            while(in<x.length&&x[in]<=x[j]+w){\n                in++;\n            }\n            count++;\n        }\n        return count;\n        \n    }\n}\n```
['Java']