给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示：
整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 <= rects.length <= 100
pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
pick 最多被调用10000次。
链接：https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from bisect import bisect_left
from random import randint
class Solution(object):
def __init__(self, rects):
"""
:type rects: List[List[int]]
"""
self.rects = rects
self.weight = []
s = 0
for rect in rects:
area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)
s += area
self.weight.append(s)
def pick(self):
"""
:rtype: List[int]
"""
index = bisect_left(self.weight, randint(1, self.weight[-1]))
rect = self.rects[index]
return [randint(rect[0], rect[2]), randint(rect[1], rect[3])]
|
