🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 850. Rectangle Area II
Сложность: hard
Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.
👨💻 Алгоритм:
1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.
2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1