Trying to explain why the intuitive solution wont work
Problem\nThe intuitive solution is randomly pick one rectangle from the rects and then create a random point within it. But this approach wont work. It took me 
### Problem\nThe intuitive solution is randomly pick one rectangle from the `rects` and then create a random point within it. But this approach wont work. It took me a while to understand, I am trying to explain it:\n\n![image](https://assets.leetcode.com/users/dqi2/image_1561169986.png)\n\nAs shown in the picture above, you have two rectangles.  Lets declare `S1` to be the set of points within rectanle 1, and `S2` to be point set within rectable 2. So, mathematically we have:\n```\nS1 = {p11, p12, p13, ........................, p1n}\nS2 = {p21, p22, p23, ......, p2m}\nn > m\n```\nObviously, you can see that `rectangle 1` is larger than `rectangle 2` and therefore `S1` has bigger size `(n > m)`. \nAccording to the problem, `"randomly and uniformily picks an integer point in the space covered by the rectangles"`. It is very difficult to understand,  lets translated it into another way of expression. \n\nIt is saying that, now I am providing you a new set `S = S1 + S2`, where `S = {p11, p12, ............, p1n, p21, p22, ........., p2m}` , **within this new set of points** that are merged together, randomly pick a point from it. What do you think of the probability of getting `p1i` and `p2j` right now ?  They are exactly the same, which is `1 / (n + m)`.\n\nNow, we can answer why the intuitive solution wont work. If you first randomy pick a rectangle, you have 50% to get either `S1` or `S2`,  how ever, once you select on rectangle, you have selected `S1` as your candidate point set, no matter how many time you try to pick you will never get the points in the second set `S2`. If size of S1 and S2 are the same, that would be ok, but if `S1` is bigger than `S2`, you will run into a problem. \n\nFor example, the chance of getting `S1` and `S2` are both `1 / 2`, so far so good. How ever, within `S1` and `S2`, the chance of getting point `p1i` and `p2j` are `1 / n` and `1 / m`. So the final chance of getting `p1i` and `p2j` are:\n```\nprobability_of_getting_p1i = 1 / (2 * n)\nprobability_of_getting_p2j = 1 / (2 * m)\n\nWhere n is the size of S1, and m is size of S2\n```\nThe probability depends on the size of two rectangle.\n\n### Solution\nSo how can we solve the problem that descibed in previous section ?  One way is to really merge all the point set of every rectangle and radnomly pick one from them, but this may  not be a good idea since it requires very hight space somplexity. What if we make the chance of getting reactangle`S1` higher than rectangle `S2` (from rects) base on the size of each of them.\nfor example, for simplification, lets assume:\n```\nn = size_of_s1 = 70\nm = size_of_s2 = 30\n\nn + m = 100\n```\n\nif we can have the chance of getting `S1` to be `70 %` and chance of getting `S2` to be `30 %`, the chance of getting `p1i` from `S1` is `1 / 70`, and chance of getting `p2j` from `S2` is `1 / 30`, we have:\n```\nprobality_of_getting_p1i = (70 / 100) * (1 / 70) = 1 / 100\n\nprobability_of_getting_p2j = (30 / 100) * (1 / 30) = 1 / 100\n```\n\nproblem sovled !\n\nSo, our mission **is to implement an algorithm that allows us to have higher chance to pick the larger rectangle**, and then generate a random point with it. Lets use code pseudo to make a rough design, still base on the previous example, imagine you have a map:\n\n```\n\nmap = \n{\n\t30: S1,\n\t30 + 70: S2\n}\n\nor \n\nmap = \n{\n  30: S1,\n  100: S2\n}\n\n\nrandomNumer = random(0, 100)\n\nif  30 < randomNumber <= 100:\n\treturn S2\nelse\n\treturn S1\n\n```\n\nIf we can design an algorithm like that, we will have 70% chance gitting S2, and 30% chance hitting S1. With number of intervals already known, we can simply use `if .. else` block or `switch` to implement this, but the problem did not specify how many rects, so the popular solution uses `TreeMap` .\n\n\n
[]