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:
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.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.
use rand::distributions::WeightedIndex;
use rand::prelude::*;
struct Solution {
rng: ThreadRng,
rects: Vec<Vec<i32>>,
size: usize,
dist: WeightedIndex<i32>,
}
impl Solution {
fn new(rects: Vec<Vec<i32>>) -> Self {
let rng = thread_rng();
let size = rects.len();
let weights: Vec<i32> = rects
.iter()
.map(|v| (v[2] - v[0] + 1) * (v[3] - v[1] + 1))
.collect();
let dist = WeightedIndex::new(weights).unwrap();
Solution {
rng,
rects,
size,
dist,
}
}
fn pick(&mut self) -> Vec<i32> {
let rect = &self.rects[self.rng.sample(&self.dist)];
let x = self.rng.gen_range(rect[0], rect[2] + 1);
let y = self.rng.gen_range(rect[1], rect[3] + 1);
vec![x, y]
}
}