You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [ai, bi, xi, yi] indicates that (ai, bi) is the bottom-left corner point of the ith rectangle and (xi, yi) is the top-right corner point of the ith rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.

Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.

Note that an integer point is a point that has integer coordinates.

Implement the Solution class:


	Solution(int[][] rects) Initializes the object with the given rectangles rects.
	int[] pick() Returns a random integer point [u, v] inside the space covered by one of the given rectangles.


&nbsp;
Example 1:

Input
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

Explanation
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]


&nbsp;
Constraints:


	1 &lt;= rects.length &lt;= 100
	rects[i].length == 4
	-109 &lt;= ai &lt; xi &lt;= 109
	-109 &lt;= bi &lt; yi &lt;= 109
	xi - ai &lt;= 2000
	yi - bi &lt;= 2000
	All the rectangles do not overlap.
	At most 104 calls will be made to pick.


class Solution:
    """
    1 <= rects.length <= 100
    rects[i].length == 4
    -10^9 <= ai < xi <= 10^9
    -10^9 <= bi < yi <= 10^9
    xi - ai <= 2000
    yi - bi <= 2000
    All the rectangles do not overlap.
    At most 10^4 calls will be made to pick.
    """

    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.n_range = list(range(len(self.rects)))
        self.weights = [(x[2] - x[0] + 1) * (x[3] - x[1] + 1) for x in rects]

    def pick(self) -> List[int]:
        rect = self.rects[choices(self.n_range, self.weights, k=1)[0]]
        return [randint(rect[0], rect[2]), randint(rect[1], rect[3])]


# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
class Solution {
    
    int[][] rects;
    TreeMap<Integer, Integer> weightedRectIndex = new TreeMap<>();
    int nPoints = 0;
    
    Random rng = new Random();

    public Solution(int[][] rects) {
        this.rects = rects;
        int index = 0;
        for (int[] rect : rects) {
		    // inserts cumulative weight key pointing to rectangle index
            weightedRectIndex.put(nPoints, index++);
            nPoints += width(rect) * height(rect);
        }
    }
    
    public int[] pick() {
	    // generates random point within total weight
        int point = rng.nextInt(nPoints);
		// finds appropriate rectangle
        var entry = weightedRectIndex.floorEntry(point);
		// find point within the current rectangle
        int rectPoint = point - entry.getKey();
        int[] rect = rects[entry.getValue()];
        return new int[]{
            rect[0] + rectPoint % width(rect), 
            rect[1] + rectPoint / width(rect)};
    }
    
    private int width(int[] rect) {
        return rect[2] - rect[0] + 1;
    }
    
    private int height(int[] rect) {
        return rect[3] - rect[1] + 1;
    }
}
class Solution {
public:
    vector<int> prefix_sum;
    vector<vector<int>> rects_vec;
    int total = 0;
    
    Solution(vector<vector<int>>& rects) {
        int cur = 0;
        for (int i = 0; i < rects.size(); ++i) {
            cur += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            prefix_sum.push_back(cur);
        }
        rects_vec = rects;
        total = cur;
    }
    
    vector<int> pick() {
        int l = 0, r = prefix_sum.size() - 1, mid = 0;
        int rand_num = rand();
        int target = (rand_num % total) + 1;
		
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (prefix_sum[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
 
        return {rand_num % (rects_vec[l][2] - rects_vec[l][0] + 1) + rects_vec[l][0],
                rand_num % (rects_vec[l][3] - rects_vec[l][1] + 1) + rects_vec[l][1]};
    }
};
/**
 /**
 * @param {number[][]} rects
 */
var Solution = function(rects) {
    this.rects = rects;
    this.map = {};
    this.sum = 0;
    // we put in the map the number of points that belong to each rect
    for(let i in rects) {
        const rect = rects[i];
        // the number of points can be picked in this rectangle
        this.sum += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
        this.map[this.sum] = i;
    }
    this.keys = Object.keys(this.map);
};

/**
 * @return {number[]}
 */
Solution.prototype.pick = function() {
    // random point pick between [1, this.sum]
    const randomPointPick = Math.floor(Math.random() * this.sum) + 1;
    
    // we look for the randomPointPick in the keys of the map
    let pointInMap;
    // the keys exists in map
    if(this.map[randomPointPick]) pointInMap = randomPointPick;
    // the key is the first in the map (we do this check before doing binary search because its out of boundery)
    else if(randomPointPick < this.keys[0]) pointInMap = this.keys[0];
    let high = this.keys.length;
    let low = 1;
    // binary search to find the closest key that bigger than randomPointPick
    while(low <= high && !pointInMap) {
        const mid = Math.floor((low + (high-low)/2));
        if(randomPointPick > this.keys[mid-1] && randomPointPick < this.keys[mid]) {
            pointInMap = this.keys[mid];
            break;
        } else if (randomPointPick > this.keys[mid]){
            low = mid+1;
        } else {
            high = mid-1;
        }
    }
    
    // we have the point, now we can get which rect belong to that point
    const pointInRects = this.map[pointInMap];
    const chosen = this.rects[pointInRects];
    const rightX = chosen[2];
    const leftX = chosen[0];
    const topY = chosen[3];
    const bottomY = chosen[1];
    const pickX = Math.floor(Math.random() * (rightX-leftX+1)) + leftX;
    const pickY = Math.floor(Math.random() * (topY-bottomY+1)) + bottomY;
    return [pickX, pickY]
};

/** 
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(rects)
 * var param_1 = obj.pick()
 */
Random Point in Non-overlapping Rectangles