497. Random Point in Non-overlapping Rectangles

Link

Solution

Calculate the range by sum up all rectangles' areas.

And randomly pick a number between( 1 ~ range) to decide which rectangle is chosen.

And then randomly pick a point from that rectangle.

    Random random;
    int range = 0;
    TreeMap<Integer, int[]> tmap;
    public Solution(int[][] rects) {
        random = new Random();
        tmap = new TreeMap<>();
        for(int[] rect : rects){
            //The point in the edge shall be included
            range += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            tmap.put(range, rect);
        }
        
    }
    
    public int[] pick() {
        // random nextInt(range) = 0 ~ range-1
        // after adding 1 : 1 ~ range
        int space = random.nextInt(range) + 1;
        int[] rect = tmap.ceilingEntry(space).getValue();
        return pick(rect);
    }
    
    public int[] pick(int[] rect){
        
        int x = rect[0] + random.nextInt(rect[2]-rect[0]+1);
        
        int y = rect[1] + random.nextInt(rect[3]-rect[1]+1);
        
        return new int[]{x,y};
    }