Random Point in Non-overlapping Rectangles

Problem Id: 497 Difficulty: Medium


Intuition

Solution


class Solution:

    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.sum = []
        total = 0
        for i in range(len(rects)):
            x1, y1, x2, y2 = rects[i]
            total += (x2 - x1 + 1) * (y2 - y1 + 1)
            self.sum.append(total)
        self.total = total

    def pick(self) -> List[int]:
        choice = random.randint(1, self.total)
        if choice <= self.sum[0]:
            j = 0
        else:
            i = 0
            j = len(self.rects) - 1
            while j - i > 1:
                mid = (i + j) // 2
                if self.sum[mid] < choice:
                    i = mid
                else:
                    j = mid

        x1, y1, x2, y2 = self.rects[j]
        x = random.randint(x1, x2)
        y = random.randint(y1, y2)
        return x, y


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