Ctrl K

Плитки складываются в прямоугольник

Сложная
Дан список прямоугольных плиток tiles, стороны которых параллельны осям координат. Плитка [x1, y1, x2, y2] имеет левый нижний угол в точке (x1, y1) и правый верхний — в (x2, y2). Верните True, если все плитки вместе покрывают некоторый прямоугольник ровно: без дыр и без наложений. Иначе верните False.
Пример 1
tiles=[[0, 0, 2, 1], [2, 0, 3, 2], [0, 1, 2, 2]] → True

Две плитки 2 × 1 лежат одна над другой слева, плитка 1 × 2 стоит справа — вместе ровно прямоугольник 3 × 2.

Пример 2
tiles=[[0, 0, 2, 2], [1, 0, 3, 2]] → False

Плитки накладываются друг на друга в полосе от x = 1 до x = 2.

Пример 3
tiles=[[0, 0, 1, 1], [2, 0, 3, 1]] → False

Между плитками остаётся пустая клетка, так что прямоугольника нет.

Ограничения
  • 1 ≤ len(tiles) ≤ 2·10⁴
  • len(tiles[i]) = 4
  • -10⁵ ≤ x1 < x2 ≤ 10⁵
  • -10⁵ ≤ y1 < y2 ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКонтур городской застройки СложнаяПлощадь объединения прямоугольников СложнаяСамый узкий отрезок для каждой точки СложнаяЛиния, делящая площадь пополам СложнаяОбщие окна в расписаниях Средняя
загружаем Python…
Вход
tiles=[[0, 0, 2, 1], [2, 0, 3, 2], [0, 1, 2, 2]]
Ожидается
True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 92 теста на сервере, включая скрытые.