Question

2250. 统计包含每个点的矩形数目

English Version

题目描述

给你一个二维整数数组 rectangles ，其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 高为 hi 。给你一个二维整数数组 points ，其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。

第 i 个矩形的 左下角 在 (0, 0) 处，右上角 在 (li, hi) 。

请你返回一个整数数组_ _count ，长度为 points.length，其中_ _count[j]是 包含 第_ _j 个点的矩形数目。

如果 0 <= xj <= li 且 0 <= yj <= hi ，那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。

 

示例 1：

输入：rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
输出：[2,1]
解释：
第一个矩形不包含任何点。
第二个矩形只包含一个点 (2, 1) 。
第三个矩形包含点 (2, 1) 和 (1, 4) 。
包含点 (2, 1) 的矩形数目为 2 。
包含点 (1, 4) 的矩形数目为 1 。
所以，我们返回 [2, 1] 。

示例 2：

输入：rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
输出：[1,3]
解释：
第一个矩形只包含点 (1, 1) 。
第二个矩形只包含点 (1, 1) 。
第三个矩形包含点 (1, 3) 和 (1, 1) 。
包含点 (1, 3) 的矩形数目为 1 。
包含点 (1, 1) 的矩形数目为 3 。
所以，我们返回 [1, 3] 。

 

提示：

• 1 <= rectangles.length, points.length <= 5 * 104
• rectangles[i].length == points[j].length == 2
• 1 <= li, xj <= 109
• 1 <= hi, yj <= 100
• 所有 rectangles 互不相同 。
• 所有 points 互不相同 。

解法

方法一：排序 + 二分

class Solution:
  def countRectangles(
    self, rectangles: List[List[int]], points: List[List[int]]
  ) -> List[int]:
    d = defaultdict(list)
    for x, y in rectangles:
      d[y].append(x)
    for y in d.keys():
      d[y].sort()
    ans = []
    for x, y in points:
      cnt = 0
      for h in range(y, 101):
        xs = d[h]
        cnt += len(xs) - bisect_left(xs, x)
      ans.append(cnt)
    return ans

class Solution {
  public int[] countRectangles(int[][] rectangles, int[][] points) {
    int n = 101;
    List<Integer>[] d = new List[n];
    Arrays.setAll(d, k -> new ArrayList<>());
    for (int[] r : rectangles) {
      d[r[1]].add(r[0]);
    }
    for (List<Integer> v : d) {
      Collections.sort(v);
    }
    int m = points.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      int x = points[i][0], y = points[i][1];
      int cnt = 0;
      for (int h = y; h < n; ++h) {
        List<Integer> xs = d[h];
        int left = 0, right = xs.size();
        while (left < right) {
          int mid = (left + right) >> 1;
          if (xs.get(mid) >= x) {
            right = mid;
          } else {
            left = mid + 1;
          }
        }
        cnt += xs.size() - left;
      }
      ans[i] = cnt;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
    int n = 101;
    vector<vector<int>> d(n);
    for (auto& r : rectangles) d[r[1]].push_back(r[0]);
    for (auto& v : d) sort(v.begin(), v.end());
    vector<int> ans;
    for (auto& p : points) {
      int x = p[0], y = p[1];
      int cnt = 0;
      for (int h = y; h < n; ++h) {
        auto& xs = d[h];
        cnt += xs.size() - (lower_bound(xs.begin(), xs.end(), x) - xs.begin());
      }
      ans.push_back(cnt);
    }
    return ans;
  }
};

func countRectangles(rectangles [][]int, points [][]int) []int {
  n := 101
  d := make([][]int, 101)
  for _, r := range rectangles {
    d[r[1]] = append(d[r[1]], r[0])
  }
  for _, v := range d {
    sort.Ints(v)
  }
  var ans []int
  for _, p := range points {
    x, y := p[0], p[1]
    cnt := 0
    for h := y; h < n; h++ {
      xs := d[h]
      left, right := 0, len(xs)
      for left < right {
        mid := (left + right) >> 1
        if xs[mid] >= x {
          right = mid
        } else {
          left = mid + 1
        }
      }
      cnt += len(xs) - left
    }
    ans = append(ans, cnt)
  }
  return ans
}

function countRectangles(rectangles: number[][], points: number[][]): number[] {
  const n = 101;
  let ymap = Array.from({ length: n }, v => []);
  for (let [x, y] of rectangles) {
    ymap[y].push(x);
  }
  for (let nums of ymap) {
    nums.sort((a, b) => a - b);
  }
  let ans = [];
  for (let [x, y] of points) {
    let count = 0;
    for (let h = y; h < n; h++) {
      const nums = ymap[h];
      let left = 0,
        right = nums.length;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (x > nums[mid]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      count += nums.length - right;
    }
    ans.push(count);
  }
  return ans;
}