LeetCode [497] Random Point in Non-overlapping Rectangles

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

1. An integer point is a point that has integer coordinates. 
2. A point on the perimeter of a rectangle is included in the space covered by the rectangles. 
3. ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
4. length and width of each rectangle does not exceed 2000.
5. 1 <= rects.length <= 100
6. pick return a point as an array of integer coordinates [p_x, p_y]
7. pick is called at most 10000 times.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { map<int, int> hash; int sum; vector<vector<int>> rectangles; public: Solution(vector<vector<int>> &rects) { sum = 0; rectangles = rects; for (int i = 0; i < rects.size(); ++i) { sum += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1); hash[sum] = i; } } vector<int> pick() { //randomly pick a vector proportional to its size int r = rand() % sum; auto it = hash.upper_bound(r); //generate a random vector inside that rectangle int x = rand() % (rectangles[it->second][2] - rectangles[it->second][0] + 1) + rectangles[it->second][0]; int y = rand() % (rectangles[it->second][3] - rectangles[it->second][1] + 1) + rectangles[it->second][1]; return vector<int>{x, y}; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(rects); * vector<int> param_1 = obj->pick(); */