Random Point in Non-overlapping Rectangles

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","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.

Example 2:

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

class Solution {
   
public:
     vector<vector<int> > rects;
    vector<int> q;
    Solution(vector<vector<int>>& rects) 
    {
        int sum=0;
        for(auto p:rects)
        {
        sum+=(p[2]-p[0]+1)*(p[3]-p[1]+1);
            q.push_back(sum);
        }
        
        this->rects=rects;
    }
    
    vector<int> pick() {
        int i=lower_bound(q.begin(),q.end(),rand()%q.back()+1)-q.begin();
        int d1=rects[i][2]-rects[i][0]+1;
        int d2=rects[i][3]-rects[i][1]+1;
        int x=rand()%d1;
        int y=rand()%d2;
        
        return {rects[i][0]+x,rects[i][1]+y};
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */