leetcode-go/medium/497.random-point-in-non-overlapping-rectangles.go

type Solution struct {
	size  int
	rects [][]int
	areas []int
}

func Constructor(rects [][]int) (sol Solution) {
	sol.size = len(rects)
	sol.areas = make([]int, sol.size+1)
	sol.rects = rects
	for i := 0; i < sol.size; i++ {
		r := rects[i]
		w, h := r[2]-r[0]+1, r[3]-r[1]+1
		sol.areas[i+1] = sol.areas[i] + w*h
	}
	return
}

func (this *Solution) Pick() []int {
	idx := rand.Intn(this.areas[this.size])
	beg, end := 1, this.size
	for beg <= end {
		mid := beg + (end-beg)/2
		if this.areas[mid] < idx {
			beg = mid + 1
		} else {
			end = mid - 1
		}
	}
	if this.areas[beg] != idx {
		beg--
	}
	pos := idx - this.areas[beg]
	r := this.rects[beg]
	w := r[2] - r[0] + 1
	dx, dy := pos%w, pos/w
	return []int{r[0] + dx, r[1] + dy}
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(rects);
 * param_1 := obj.Pick();
 */