> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/497-random-point-in-non-overlapping-rectangles.md).

# 497 Random Point in Non-overlapping Rectangles

## 497. [Random Point in Non-overlapping Rectangles](https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/description/)

## 1. Question

Given a list of**non-overlapping** axis-aligned rectangles`rects`, write a function`pick`which randomly and uniformily picks an**integer point**in 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. `i`th 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 exceed`2000`.
5. `1 <= rects.length <= 100`
6. `pick`return a point as an array of integer coordinates `[p_x, p_y]`
7. `pick`is called at most`10000`times.

**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 rectangles`rects`.`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大于等于随机数

```java
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**

```java
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)