497.md

497. Random Point in Non-overlapping Rectangles

Solution 1

class Solution(object):

    def __init__(self, rects):
        """
        :type rects: List[List[int]]
        """
        self.rects = rects
        self.sum = [0]
        for a, b, x, y in rects:
            self.sum.append(self.sum[-1] + (x - a + 1) * (y - b + 1))

    def pick(self):
        """
        :rtype: List[int]
        """
        t = randrange(self.sum[-1])
        rect_ind = bisect_right(self.sum, t) - 1
        a, b, x, y = self.rects[rect_ind]
        da, db = divmod(t - self.sum[rect_ind], y - b + 1)
        return [a + da, b + db]

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