Случайная точка в задаче о непересекающихся прямоугольниках
Имея список непересекающихся выровненных по оси прямоугольников rects
, напишите функцию pick
, которая случайным образом и равномерно выбирает целочисленную точку в пространстве, покрытом прямоугольниками.
Примечание:
- Целочисленная точка – это точка с целочисленными координатами.
- Точка на периметре прямоугольника включена в пространство, занимаемое прямоугольниками.
i
th прямоугольник =rects[i]
=[x1,y1,x2,y2]
, где[x1, y1]
— целочисленные координаты левого нижнего угла, а[x2, y2]
— целочисленные координаты правого верхнего угла.- длина и ширина каждого прямоугольника не превышает
2000
. 1 <= rects.length <= 100
pick
вернуть точку в виде массива целочисленных координат[p_x, p_y]
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.