Tuesday, April 30, 2019

LeetCode [497] Random Point in Non-overlapping Rectangles

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. 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 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
    map<int, int> hash;
    int sum;
    vector<vector<int>> rectangles;
  public:
    Solution(vector<vector<int>> &rects)
    {
        sum = 0;
        rectangles = rects;
        for (int i = 0; i < rects.size(); ++i)
        {
            sum += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            hash[sum] = i;
        }
    }

    vector<int> pick()
    {
        //randomly pick a vector proportional to its size
        int r = rand() % sum;
        auto it = hash.upper_bound(r);

        //generate a random vector inside that rectangle
        int x = rand() % (rectangles[it->second][2] - rectangles[it->second][0] + 1) + rectangles[it->second][0];
        int y = rand() % (rectangles[it->second][3] - rectangles[it->second][1] + 1) + rectangles[it->second][1];
        return vector<int>{x, y};
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */
at

No comments:

Post a Comment