How does binary search help in solving the Random Point in Non-overlapping Rectangles problem?

Binary search is used to efficiently select one rectangle based on the cumulative area of all rectangles, ensuring each rectangle is equally likely to be chosen.

What is the role of reservoir sampling in this problem?

Reservoir sampling is used to randomly select a point inside the chosen rectangle with equal probability, ensuring fairness in point selection.

What is the time complexity of this solution?

The time complexity for preprocessing the rectangles is O(n), and each query is answered in O(log n) time due to binary search over the prefix sum array.

How do you ensure that points on the perimeter are included in the solution?

The solution explicitly considers the perimeter of the rectangle as part of the valid point space, ensuring that points on the boundary are equally likely to be selected.

Can this solution be optimized further for more queries?

The current solution is already efficient with O(log n) query time. Further optimizations would likely focus on the data structure used for maintaining rectangles or handling dynamic updates.

#497

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

非重叠矩形中的随机点

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点， (xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有…

数组数学二分查找蓄水池抽样前缀和

题目描述

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意 ，整数点是具有整数坐标的点。

实现 Solution 类:

Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

示例 1：

输入: 
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出: 
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]

提示：

1 <= rects.length <= 100
rects[i].length == 4
-10⁹ <= a_i < x_i <= 10⁹
-10⁹ <= b_i < y_i <= 10⁹
x_i - a_i <= 2000
y_i - b_i <= 2000
所有的矩形不重叠。
pick 最多被调用 10⁴ 次。

lightbulb

解题思路

方法一：前缀和 + 二分查找

将矩形面积求前缀和 $s$ ，然后随机获取到一个面积 $v$ ，利用二分查找定位到是哪个矩形，然后继续随机获取该矩形的其中一个整数点坐标即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.s = [0] * len(rects)
        for i, (x1, y1, x2, y2) in enumerate(rects):
            self.s[i] = self.s[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1)

    def pick(self) -> List[int]:
        v = random.randint(1, self.s[-1])
        idx = bisect_left(self.s, v)
        x1, y1, x2, y2 = self.rects[idx]
        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()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain how binary search is applied to pick a rectangle based on area distribution?
question_mark
Does the candidate understand how to maintain equal probability for point selection within the chosen rectangle?
question_mark
Can the candidate efficiently handle multiple queries with preprocessing, ensuring that the solution scales?

warning

常见陷阱

外企场景

error
Failing to account for the non-overlapping condition, which simplifies the problem by ensuring there is no need for complex collision detection.
error
Misunderstanding how to use binary search to select rectangles based on area rather than simply picking a random rectangle.
error
Not ensuring that every point within the selected rectangle is equally likely to be chosen, especially with multiple queries.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modifying the problem to handle overlapping rectangles would require additional complexity in the rectangle selection process.
arrow_right_alt
Extending the problem to allow weighted probability for each rectangle would involve adjusting the prefix sum logic to account for different weights.
arrow_right_alt
Introducing dynamic rectangle modifications (e.g., adding or removing rectangles) would require an updated approach for maintaining the prefix sum array.

help

常见问题

外企场景

继续练习

#528 按权重随机选择 #363 矩形区域不超过 K 的最大数值和 #710 黑名单中的随机数