497.py

__________________________________________________________________________________________________
sample 176 ms submission
class Solution:

    def __init__(self, rects: List[List[int]]):
        self.rects, self.ranges, sm = rects, [0], 0
        for x1,y1,x2,y2 in rects:
            sm += (x2 - x1 + 1) * (y2 - y1 + 1)
            self.ranges.append(sm)

    def pick(self) -> List[int]:
        n = random.randrange(self.ranges[-1])
        i = bisect.bisect(self.ranges, n)
        n -= self.ranges[i - 1]
        x1,y1,x2,y2 = self.rects[i - 1]
        return [x1 + n % (x2 - x1 + 1), y1 + n // (x2 - x1 + 1)]

# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
__________________________________________________________________________________________________
sample 184 ms submission
import random
class Solution:

    def __init__(self, rects: List[List[int]]):
        # intuition, the points can be generated by x/y separately
        # then we just have to store 2D intervals for x/y
        # since the problem only contains non-overlap rectangle
        # so we can insert by natural ordering of the intervals
        # WRONG! we can't do it separately as the x and y are highly coupled
        # so the rectangle can be defined!
        # naive way of picking one rectangle and then picking point in it
        # is actually weighted random by the area of the rectangle,
        # points in smaller rectangle will have a higher probability to be picked
        # we can calculate the total area, and then pick one point from total area
        # 
        self.data =rects
        self.area = 0
        for x1,y1,x2,y2 in self.data:
            self.area+= (x2-x1+1)*(y2-y1+1)
            
    def pick(self) -> List[int]:
        #idx = random.randrange(len(self.data))
        #x1, y1, x2,y2 = self.data[idx]
        #return random.randrange(x1, x2+1), random.randrange(y1, y2+1)
        p = random.randrange(self.area)
        for x1,y1,x2,y2 in self.data:
            a = (x2-x1+1)*(y2-y1+1)
            if p<a:
                return x1+p//(y2-y1+1), y1+p%(y2-y1+1)
            p-=a
        
# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
__________________________________________________________________________________________________