497. random points in non overlapping rectangles

497. Random points in non overlapping rectangles 【 Medium question 】【 A daily topic 】

Ideas ：【 Pool sampling 】

Write it in detail tomorrow , In the eye , I'm really not free today ~

Code ：

class Solution {
    

    int[][] recs;
    Random random;

    public Solution(int[][] rects) {
    
        this.recs = rects;
        this.random = new Random();
    }
    
    public int[] pick() {
    
        //idx  Record the subscript of the currently selected rectangle  cur  Record the number of points in the current rectangle  curSum  Record after adding the point in the current rectangle , How many points are there in total 
        int idx = 0,n = recs.length;
        long cur = 0,curSum = 0;
        // Every time we traverse a rectangle , That is, calculate the number of points in the current rectangle  cur, Then calculate how many points there are in total curSum
        // Randomly select an integer point covered by a rectangle , So to ensure fairness , The probability of extracting the midpoint of the rectangle currently traversed should be  cur/curSum
        for (int i = 0; i < n; i++) {
    
            int x1 = recs[i][0],y1 = recs[i][1],x2 = recs[i][2],y2 = recs[i][3];
            cur = (long) (x2 - x1 + 1) * (y2 - y1 + 1);
            curSum += cur;
            if (random.nextLong(curSum + 1) < cur){
    
                idx = i;
            }
        }
        int x1 = recs[idx][0],y1 = recs[idx][1], x2 = recs[idx][2],y2 = recs[idx][3];
        return new int[]{
    x1 + random.nextInt(x2 - x1 + 1),y1 + random.nextInt(y2 - y1 + 1)};
    }
}

/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(rects); * int[] param_1 = obj.pick(); */