Problem

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:

An integer point is a point that has integer coordinates.
A point on the perimeter of a rectangle is included in the space covered by the rectangles.
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.
length and width of each rectangle does not exceed 2000.
1 <= rects.length <= 100
pick return a point as an array of integer coordinates [p_x, p_y]
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.

Solution: Binary Search

Same as LeetCode 880. Random Pick with Weight

Use area of the rectangles as weights.

Time complexity: Init: O(n) Pick: O(logn)

Space complexity: O(n)

// Author: Huahua

// Running time: 92 ms

class Solution {

public:

Solution(vector<vector<int>> rects): rects_(std::move(rects)) {

sums_ = vector<int>(rects_.size());

for (int i = 0; i < rects_.size(); ++i) {

sums_[i] = (rects_[i][2] - rects_[i][0] + 1) * (rects_[i][3] - rects_[i][1] + 1);

if (i > 0) sums_[i] += sums_[i - 1];

}

vector<int> pick() {

const int s = nextInt(sums_.back()) + 1;

int index = lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();

const auto& rect = rects_[index];

return {rect[0] + nextInt(rect[2] - rect[0] + 1),

rect[1] + nextInt(rect[3] - rect[1] + 1)};

}

private:

vector<int> sums_;

vector<vector<int>> rects_;

// Returns a random int in [0, n - 1]

int nextInt(int n) {

return rand() / static_cast<double>(RAND_MAX) * n;

}

};

Posts tagged as “weighted”

花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles

Problem

Solution: Binary Search

Related Problems