Python3 O(log(n)) solution using statistical ideas
I am currently studying statistics, so thought it would be a nice practice to apply a bit of that here.\n\nWhat we want here, per requirement, is that every int
I am currently studying statistics, so thought it would be a nice practice to apply a bit of that here.\n\nWhat we want here, per requirement, is that every integer point has the same probability of being picked. Now, since points are distributed among rectangles we could use a sampling technique where we pick first a rectangle based on its "weight" (size), and then we use simple random sampling within such rectangle. I actually made the exercise of proving this implicit claim with two rectangles.\n\nSay we have 10 points, where 6 live in first rectangle and 4 live in the other one. We could think of a decision tree where first branching is done by picking the rectangle and second branching is done by picking the actual point within each rectangle (so first branch has 6 leaves and second branch has 4).\n\nSince we know that we want to use simple random sampling (SRS) within each rectangle, we know that:\n\nP(x_i | R_1) = 1/6 for i in {1,2,3,4,5,6}\nP(x_i | R_2) = 1/4 for i in {7, 8, 9, 10}\n\nwhere x_i is the event of picking element x_i, and R_j is the event of picking rectangle 1 or 2.\n\nNow, using definition of conditional probability (used backwards) we know that the probability of reaching every leaf in decision tree is given by:\n\nP(R_j and x_i) = P(R_j) P(x_i | R_j)\n\nand we would like the following equality to hold, if every leaf in the decision tree is to be equally likely to be picked (as each leaf represents one of the integer points from our total set):\n\nP(R_1) P(x_i | R_1) = P(R_2) P(x_i | R_2)\n\nReplacing the constants we setup for our example, equality becomes:\n\nP(R_1) (1/6) = P(R_2) (1/4)\n\nSince we just have two rectangles P(R_2) = 1 - P(R_1), hence\n\nP(R_1) (1/6) = (1 - P(R_1)) (1/4)\n\nSolving that linear equation for P(R_1) will give us 0.6, hence leaving P(R_2) = 0.4. And that is precisely the intuitive "weight" we could think of assigning, if wanting to make probability proportional to the size of each rectangle. I did not do it, but suspect this proof-template could we extended to any probabilities and number of rectangles. So, let us buy for now that such sampling technique is valid.\n\nNow, one way of implementing it is to to compute the percentages out of the total that each rectangle contributes with, and think that as the desired probability to pick such rectangle. Then we could use an enumerative sampling algorithm like the one mentioned at page 27 of this presentation:\n\nhttp://www.eustat.eus/productosServicios/52.1_Unequal_prob_sampling.pdf\n\nIn such algorithm we compute the the cumulative sum of probabilities for each rectangle, using the order they have already in input param. Such cumulative probability could be thought as the high end of a probabilities range. Then the algorithm generates a uniformly random number in [0,1] and searches for the rectangle whose probability range contains such random number. We can do such search efficiently with a binary search.\n\nOnce we picked the rectangle, we proceed to generate a random number from there by using another result from Probability: in order to select a random point within a rectangle, we can think of two independent random variables for each axis. Hence, generating one tuple where first element is uniform random number for axis-X range, and second element is uniform random number for axis-Y range; should be equivalent to picking one point randomly from rectangle formed by cartesian product of those two ranges. See proof/comment from this discussion (The one starting with "That statement is incorrect, direct product of two independent uniform measures is a uniform measure. This can be shown as follows ...")\n\nhttps://stackoverflow.com/questions/6884003/generate-a-random-point-within-a-rectangle-uniformly\n\nAnd voil\xE0, putting all that together gives following snippet. At the time of this writing, it beats all the Python3 solutions.\n\n```\nfrom bisect import bisect_left\nfrom random import random, randint\n\nclass Solution:\n\n    def __init__(self, rects):\n        self.rects = rects\n        self.cump = []\n        total = 0\n        for x1,y1,x2,y2 in rects:\n            w, h = x2 - x1 + 1, y2 - y1 + 1\n            total += w * h\n            self.cump.append(total)\n        for i in range(len(self.cump)):\n            self.cump[i] /= total\n\n    def pick(self):\n        i = bisect_left(self.cump, random())\n        x1,y1,x2,y2 = self.rects[i]\n        x = randint(x1, x2)\n        y = randint(y1, y2)\n        return (x,y)\n```
[]