0%

### 题目描述

Given a list of non-overlapping axis-aligned rectangles `rects`, write a function `pick` which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:
1.An integer point is a point that has integer coordinates.
2.A point on the perimeter of a rectangle is included in the space covered by the rectangles.
3.`i`th rectangle = `rects[i] = [x1,y1,x2,y2]`, where `[x1, y1]` are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
4.length and width of each rectangle does not exceed `2000`.
5.`1 <= rects.length <= 100`
6.pick return a point as an array of integer coordinates `[p_x, p_y]`
7.`pick` is called at most `10000` times.

### 例子

#### 例子 1

Input:
`["Solution","pick","pick","pick"]`
`[[[[1,1,5,5]]],[],[],[]]`
Output:
`[null,[4,1],[4,1],[3,3]]`

#### 例子 2

Input:
`["Solution","pick","pick","pick","pick","pick"]`
`[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]`
Output:
`[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]`

#### Explanation of Input Syntax

The input is two lists: the subroutines called and their arguments. `Solution`‘s constructor has one argument, the array of rectangles `rects`. `pick` has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

### 解题思路

• 针对每一个矩形，可选的点是所有坐标为整数的点，并且四条边覆盖点也在可选择范围内。这意味着针对矩形 `[0, 0, 1, 1]` 我们实际上可选的点有四个：`[0, 0], [0, 1], [1, 0], [1, 1]`。这一点在后续选择点坐标系要尤其注意选择的范围是 边长+1，并且计算面积时不能简单地用长 × 宽来代替，而是 （长 + 1）× （宽 + 1），代表可选的点的个数。
• 针对所有覆盖面积随机取点，因为矩形的面积不一定相同，所以均匀地从矩形数组中选矩形会导致出现问题。选取矩形的概率应该和其面积成正相关，我们可以利用转盘的思想将所有矩形的面积计算出来，然后在总面积范围内随机选取一个值，看那个值落在哪个矩形上。为了提高搜索速度可以直接使用 STL 中的 `lower_bound()` 使用二分查找进行搜索

• 时间复杂度：Solution: O(n)， Pick: O(logn)
• 空间复杂度：O(n)