发表于 2024.07.31

• 该题目只涉及到x坐标，y坐标是无关紧要的(矩形无高度限制)。本质就是尽可能地使用最少的矩形，使得其宽度覆盖所有的点。可先对所有点的x坐标进行排序，然后使用贪心法，每次取出一个当前剩余的最大的x坐标(作为新矩形的右边界)，然后再取出尽可能多的x坐标填充在矩形内，使得其差值不超过w即可。

  class Solution:
      def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
          x_list = sorted({x for x, _ in points})
          ans = 0
          while x_list:
              r = x_list.pop()
              while x_list and r - x_list[-1] <= w:
                  x_list.pop()
              ans += 1
          return ans

  C++的做法：

  class Solution {
  public:
      int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
          vector<int> x_list;
          for (auto &point : points) x_list.push_back(point[0]);
          sort(x_list.begin(), x_list.end());
          int ans = 0;
          int cur_index = x_list.size() - 1;
          while (cur_index >= 0) {
              auto r_bound = x_list[cur_index--];
              while (cur_index >= 0 && r_bound - x_list[cur_index] <= w) cur_index--;
              ++ans; 
          }
          return ans;
      }
  };

• LC 题目链接