LeetCode 497. Random Point in Non-overlapping Rectangles

Posted on | In |
Words count in article: 391 | Reading time ≈ 2

题目

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:

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

Example 2:

1
2
3
4
5
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. Choose a rect, then choose a point inside it.
  2. The bigger the rectangle, the higher the probability of it getting chosen.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import random

class Solution:

    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        
        # self.weights = []
        # for rect in rects:
        #     x1, y1, x2, y2 = rect
        #     area = (x2-x1+1)*(y2-y1+1)
        #     self.weights.append(area)
        
        self.weights = [(x2-x1+1)*(y2-y1+1) for x1, y1, x2, y2 in rects]
        sum_of_weights = sum(self.weights)
        self.weights = [x/sum_of_weights for x in self.weights]
        

    def pick(self) -> List[int]:
        rect = random.choices(
            population=self.rects,
            weights=self.weights,
            k=1
        )[0]  # random.choices returns a list, we extract the first (and only) element.

        x1, y1, x2, y2 = rect  # tuple unpacking
        
        rnd_x = random.randint(x1, x2)
        rnd_y = random.randint(y1, y2)
        return [rnd_x, rnd_y]
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()