Случайная точка в задаче о непересекающихся прямоугольниках

Имея список непересекающихся выровненных по оси прямоугольников rects, напишите функцию pick, которая случайным образом и равномерно выбирает целочисленную точку в пространстве, покрытом прямоугольниками.

Примечание:

  1. Целочисленная точка – это точка с целочисленными координатами.
  2. Точка на периметре прямоугольника включена в пространство, занимаемое прямоугольниками.
  3. ith прямоугольник = rects[i] = [x1,y1,x2,y2], где [x1, y1] — целочисленные координаты левого нижнего угла, а [x2, y2] — целочисленные координаты правого верхнего угла.
  4. длина и ширина каждого прямоугольника не превышает 2000.
  5. 1 <= rects.length <= 100
  6. pick вернуть точку в виде массива целочисленных координат [p_x, p_y]
  7. pick вызывается не более 10000 раз.

Пример 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Пример 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]]

Объяснение входного синтаксиса:

На вход подаются два списка: вызываемые подпрограммы и их аргументы. Конструктор Solution имеет один аргумент, массив прямоугольников rects. pick не имеет аргументов. Аргументы всегда обертываются списком, даже если его нет.

Решение

Здесь вы можете увидеть производительность моего решения (имейте в виду, что Runtime может варьироваться в зависимости от сервера):

Вы можете подписаться на меня в LinkedIn.