Python [Probability/Monte Carlo]
This is a straightforward idea from probability theory. Say you have two rectangles, the first one contains 7 points inside and the second one contains 3. A ran
This is a straightforward idea from probability theory. Say you have two rectangles, the first one contains 7 points inside and the second one contains 3. A randomly drawn point has a probability of coming from the first rectangle equal to 0.7. So you calculate the number of points in each rectangle, and then use the inverse CDF* rule to simulate a random draw of rectangles based on the number of points they contain. (So you select the first rectangle with probability 0.7 in the example above.) Once you pick the rectangle, choose any point uniformly at random.\n\nCDF rule is at the core of simulations, Monte Carlo methods, and many machine learning algorithms.\n\nTime: `O(K)` where `K` is the number of rectangles. This is where we calculate the weights in the constructor.\nSpace: `O(K)` as we store the rectangle coordinates.\n\n*CDF: Cumulative distribution function\n\n```\nimport random\nimport bisect\nclass Solution:\n    def __init__(self, rects: List[List[int]]):\n        self.rects = rects\n        #\n        weig, c = [], 0\n        for rect in rects:\n            x1, y1, x2, y2 = rect\n            c += (x2-x1+1)*(y2-y1+1)\n            weig.append(c)\n        self.weigc = [e/c for e in weig]\n        \n        \n    def pick(self) -> List[int]:\n        u = random.random()\n        ix = bisect.bisect_left(self.weigc, u)\n        x1, y1, x2, y2 = self.rects[ix]\n        x = random.randint(x1,x2)\n        y = random.randint(y1,y2)\n        return [x,y]\n```
[]