Press "Enter" to skip to content

花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles

Problem

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. ith 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 rectspick has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Same as LeetCode 880. Random Pick with Weight

Use area of the rectangles as weights.

Time complexity: Init: O(n) Pick: O(logn)

Space complexity: O(n)

Related Problems

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply

Mission News Theme by Compete Themes.