count-number-of-rectangles-containing-each-point

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 2D integer array <code>rectangles</code> where <code>rectangles[i] = [li, hi]</code> indicates that <code>ith</code> rectangle has a length of <code>li</code> and a height of <code>hi</code>. You are also given a 2D integer array <code>points</code> where <code>points[j] = [xj, yj]</code> is a point with coordinates <code>(xj, yj)</code>.

The <code>ith</code> rectangle has its bottom-left corner point at the coordinates <code>(0, 0)</code> and its top-right corner point at <code>(li, hi)</code>.

Return an integer array <code>count</code> of length <code>points.length</code> where <code>count[j]</code> is the number of rectangles that contain the <code>jth</code> point.

The <code>ith</code> rectangle contains the <code>jth</code> point if <code>0 &lt;= xj &lt;= li</code> and <code>0 &lt;= yj &lt;= hi</code>. Note that points that lie on the edges of a rectangle are also considered to be contained by that rectangle.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example1.png" style="width: 300px; height: 509px;" />
<pre>
Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
Output: [2,1]
Explanation: 
The first rectangle contains no points.
The second rectangle contains only the point (2, 1).
The third rectangle contains the points (2, 1) and (1, 4).
The number of rectangles that contain the point (2, 1) is 2.
The number of rectangles that contain the point (1, 4) is 1.
Therefore, we return [2, 1].
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example2.png" style="width: 300px; height: 312px;" />
<pre>
Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
Output: [1,3]
Explanation:
The first rectangle contains only the point (1, 1).
The second rectangle contains only the point (1, 1).
The third rectangle contains the points (1, 3) and (1, 1).
The number of rectangles that contain the point (1, 3) is 1.
The number of rectangles that contain the point (1, 1) is 3.
Therefore, we return [1, 3].
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= rectangles.length, points.length &lt;= 5 * 104</code></li>
	<li><code>rectangles[i].length == points[j].length == 2</code></li>
	<li><code>1 &lt;= li, xj &lt;= 109</code></li>
	<li><code>1 &lt;= hi, yj &lt;= 100</code></li>
	<li>All the <code>rectangles</code> are unique.</li>
	<li>All the <code>points</code> are unique.</li>
</ul>

countRectangles

Count Number of Rectangles Containing Each Point

Queries on Number of Points Inside a Circle

queries-on-number-of-points-inside-a-circle

统计一个圆中点的数目

Binary Indexed Tree

Array

Hash Table

Binary Search

Sorting

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

第&nbsp;<code>i</code>&nbsp;个矩形的 左下角&nbsp;在&nbsp;<code>(0, 0)</code>&nbsp;处，右上角&nbsp;在&nbsp;<code>(li, hi)</code>&nbsp;。

请你返回一个整数数组&nbsp;<code>count</code>&nbsp;，长度为&nbsp;<code>points.length</code>，其中&nbsp;<code>count[j]</code>是 包含 第&nbsp;<code>j</code>&nbsp;个点的矩形数目。

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

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example1.png" style="width: 300px; height: 509px;">

<pre>输入：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] 。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/example2.png" style="width: 300px; height: 312px;">

<pre>输入：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] 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= rectangles.length, points.length &lt;= 5 * 104</code></li>
	<li><code>rectangles[i].length == points[j].length == 2</code></li>
	<li><code>1 &lt;= li, xj &lt;= 109</code></li>
	<li><code>1 &lt;= hi, yj &lt;= 100</code></li>
	<li>所有&nbsp;<code>rectangles</code>&nbsp;互不相同&nbsp;。</li>
	<li>所有&nbsp;<code>points</code> 互不相同&nbsp;。</li>
</ul>