497 Random Point in Non-overlapping Rectangles

497. Random Point in Non-overlapping Rectangles

1. Question

Given a list ofnon-overlapping axis-aligned rectanglesrects, write a functionpickwhich randomly and uniformily picks aninteger pointin 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 exceed2000.

5. 1 <= rects.length <= 100

6. pickreturn a point as an array of integer coordinates [p_x, p_y]

7. pickis called at most10000times.

Example 1:

Input: 

["Solution","pick","pick","pick"]

[[[[1,1,5,5]]],[],[],[]]
Output: 

[null,[4,1],[4,1],[3,3]]

Example 2:

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 rectanglesrects.pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

2. Implementation

(1) TreeMap

思路: 将累积面积的和放入TreeMap中，key是累积面积和，value是对应矩阵的index。调用pick()时，我们生成在[1, totalArea]的随机数，然后再通过treemap找到这个随机数所落入的累积面积和的区间，即找到最小的key，使得key对应的value大于等于随机数

class Solution {
    TreeMap<Integer, Integer> map;
    Random rand;
    int[][] rects;
    int totalArea;

    public Solution(int[][] rects) {
        this.rects = rects;
        rand = new Random();
        map = new TreeMap();
        totalArea = 0;

        for (int i = 0; i < rects.length; i++) {
            int[] rect = rects[i];
            // 坐标是从0开始，所以计算面积时，边长都要相应加1
            totalArea += (rect[2] - rect[0] + 1) *(rect[3] - rect[1] + 1);
            map.put(totalArea, i);
        }
    }

    public int[] pick() {
        // rand.nextInt(totalArea) 会返回(0, totalArea - 1)的随机数，所以rand.nextInt(totalArea) + 1保证
        // 随机生成数在[1, totalArea]之间
        int key = map.ceilingKey(rand.nextInt(totalArea) + 1);
        return pickPointInRect(rects[map.get(key)]);
    }

    public int[] pickPointInRect(int[] rect) {
        int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
        int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
        return new int[] {x, y};
    }
}

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

(2) Cumulative Sum Array

class Solution {
    Random rand;
    int[] area;
    int totalArea;
    int[][] rects;

    public Solution(int[][] rects) {
        this.rects = rects;
        rand = new Random();
        area = new int[rects.length];
        totalArea = 0;

        for (int i = 0; i < rects.length; i++) {
            int curArea = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            if (i == 0) {
                area[i] = curArea;
            }
            else {
                area[i] = curArea + area[i - 1];
            }
        }
        totalArea = area[rects.length - 1];
    }

    public int[] pick() {
        int cumArea = rand.nextInt(totalArea) + 1;
        int index = -1;

        for (int i = 0; i < area.length; i++) {
            if (cumArea <= area[i]) {
                index = i;
                break;
            }
        }
        return pickPointInRect(rects[index]);
    }

    public int[] pickPointInRect(int[] rect) {
        int x = rect[0] + rand.nextInt(rect[2] - rect[0] + 1);
        int y = rect[1] + rand.nextInt(rect[3] - rect[1] + 1);
        return new int[] {x, y};
    }
}

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

3. Time & Space Complexity

(1) TreeMap: solution(): O(nlogn), pick(): O(logn)

(2) One Pass: solution(): O(n), pick(): O(n)