0497. Random Point in Non Overlapping Rectangles

# 497. Random Point in Non-overlapping Rectangles#

## 题目 #

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.

Example 1:

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

Example 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.

## 题目大意 #

1. 整数点是具有整数坐标的点。
2. 矩形周边上的点包含在矩形覆盖的空间中。
3. 第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
4. 每个矩形的长度和宽度不超过 2000。
5. 1 <= rects.length <= 100
6. pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
7. pick 最多被调用10000次。

## 解题思路 #

• 给出一个非重叠轴对齐矩形列表，每个矩形用左下角和右上角的两个坐标表示。要求 `pick()` 随机均匀地选取矩形覆盖的空间中的整数点。
• 这一题是第 528 题的变种题，这一题权重是面积，按权重（面积）选择一个矩形，然后再从矩形中随机选择一个点即可。思路和代码和第 528 题一样。

## 代码 #

``````
package leetcode

import "math/rand"

// Solution497 define
type Solution497 struct {
rects [][]int
arr   []int
}

// Constructor497 define
func Constructor497(rects [][]int) Solution497 {
s := Solution497{
rects: rects,
arr:   make([]int, len(rects)),
}

for i := 0; i < len(rects); i++ {
area := (rects[i] - rects[i] + 1) * (rects[i] - rects[i] + 1)
if area < 0 {
area = -area
}
if i == 0 {
s.arr = area
} else {
s.arr[i] = s.arr[i-1] + area
}
}
return s
}

// Pick define
func (so *Solution497) Pick() []int {
r := rand.Int() % so.arr[len(so.arr)-1]
//get rectangle first
low, high, index := 0, len(so.arr)-1, -1
for low <= high {
mid := low + (high-low)>>1
if so.arr[mid] > r {
if mid == 0 || so.arr[mid-1] <= r {
index = mid
break
}
high = mid - 1
} else {
low = mid + 1
}
}
if index == -1 {
index = low
}
if index > 0 {
r = r - so.arr[index-1]
}
length := so.rects[index] - so.rects[index]
return []int{so.rects[index] + r%(length+1), so.rects[index] + r/(length+1)}
}

/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(rects);
* param_1 := obj.Pick();
*/

`````` Jun 22, 2022 Edit this page