Войти Регистрация
Алгоритмы

114. Сколько экрана занимают баннеры

Сложная

На макете ленты ВКонтакте лежат рекламные и служебные блоки — прямоугольники [x1, y1, x2, y2] в пикселях, со сторонами вдоль осей, x1 < x2, y1 < y2. Блоки перекрываются: сторис поверх баннера, плашка поверх сторис.

Посчитайте общую площадь макета, закрытую хотя бы одним блоком. Перекрытие считается один раз.

Пустой список — площадь 0.

В работе: Проверка правила «реклама занимает не больше 30 % экрана» на макете с перекрытиями.

Пример 1

Ввод
rects = [[0, 0, 4, 3], [2, 1, 6, 5]]
Вывод
24

12 + 16 − перекрытие 2 · 2 = 24.

Пример 2

Ввод
rects = [[0, 0, 10, 10], [2, 2, 5, 5]]
Вывод
100

Маленький блок целиком внутри большого — 100.

Ограничения

  • 0 ≤ n ≤ 10⁴
  • 0 ≤ x1 < x2 ≤ 10⁶, 0 ≤ y1 < y2 ≤ 10⁶
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def covered_area(rects):
Сканирующая прямаяСжатие координатДерево отрезковцельO(n log n)

Источник: наша задача на данных VK. Условие пересказано своими словами.