# LeetCode: 497. 非重叠矩形中的随机点¶

## 1、题目描述¶

i 个矩形 rects [i] = [x1，y1，x2，y2]，其中[x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。

1 <= rects.length <= 100

pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。

pick 最多被调用10000次。

输入:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]

[null,[4,1],[4,1],[3,3]]


输入:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]

[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]


• 输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。

## 2、解题思路¶

• 随机选择矩形
• 在矩形中随机选择长宽
import bisect
import random

class Solution:

def __init__(self, rects: List[List[int]]):
self.rects = rects
self.weight = []
s = 0

for x1, y1, x2, y2 in rects:
s += (x2 - x1 + 1) * (y2 - y1 + 1)
self.weight.append(s)

def pick(self) -> List[int]:
index = bisect.bisect_left(self.weight,random.randint(1, self.weight[-1]))
x1, y1, x2, y2 = self.rects[index]
return [random.randint(x1, x2), random.randint(y1, y2)]
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()