Random points in non overlapping rectangle (force deduction daily question)

Random points in non overlapping rectangles



This question mainly uses The prefix and and Two points search Method
It is easy for a matrix to have a random point with medium probability , The difficulty lies in how to random matrix . for example 11 Matrix sum of 22 The random probability of matrix is different , At the same time, because the maximum area of the matrix is 10 Of 18 Power , It is also unrealistic to put all possible points into an array randomly .

In essence, the probability of random arrival of each matrix is determined by its area , So we can add up the areas of all matrices , The sum of areas is recorded as sum, stay [1,sum] Take a random number from , The matrix to which this number belongs is a random matrix , To do this, you can use prefix and plus binary search

class Solution {
    
     int[][] rects;
    int[] sum;
    int n;
    Random random = new Random();
    public Solution(int[][] rects) {
    
        this.rects = rects;
        n = rects.length;
        sum = new int[n+1];
        // The prefix and 
        for(int i=1;i<=n;i++){
    
            sum[i] = sum[i-1] + (rects[i-1][2]-rects[i-1][0] + 1) * (rects[i-1][3]-rects[i-1][1] + 1);
        }
    }
    

    public int[] pick() {
    
        int val = random.nextInt(sum[n]) + 1;
        int l = -1,r = n+1;
        while(l+1 < r){
    
            int mid = l+r>>1;
            if(val <= sum[mid]){
    
                r = mid;
            }
            else l = mid;
        }
        // Find random matrix 
        int index = r-1;//index by val Matrix of area 
		// A random point in the matrix 
        int y = random.nextInt(rects[index][3]-rects[index][1] + 1) + rects[index][1];
        int x = random.nextInt(rects[index][2]-rects[index][0] + 1) + rects[index][0];

        return new int[]{
    x, y};
    }
}