Задача: 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 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

class Solution {
    function rectangleArea($rectangles) {
        $N = count($rectangles);
        $Xvals = [];
        $Yvals = [];

        foreach ($rectangles as $rec) {
            $Xvals[$rec[0]] = true;
            $Xvals[$rec[2]] = true;
            $Yvals[$rec[1]] = true;
            $Yvals[$rec[3]] = true;
        }

        $imapx = array_keys($Xvals);
        sort($imapx);
        $imapy = array_keys($Yvals);
        sort($imapy);

        $mapx = [];
        $mapy = [];
        foreach ($imapx as $i => $v) {
            $mapx[$v] = $i;
        }
        foreach ($imapy as $i => $v) {
            $mapy[$v] = $i;
        }

        $grid = array_fill(0, count($imapx), array_fill(0, count($imapy), false));
        foreach ($rectangles as $rec) {
            for ($x = $mapx[$rec[0]]; $x < $mapx[$rec[2]]; $x++) {
                for ($y = $mapy[$rec[1]]; $y < $mapy[$rec[3]]; $y++) {
                    $grid[$x][$y] = true;
                }
            }
        }

        $ans = 0;
        for ($x = 0; $x < count($grid); $x++) {
            for ($y = 0; $y < count($grid[0]); $y++) {
                if ($grid[$x][$y]) {
                    $ans += ($imapx[$x + 1] - $imapx[$x]) * ($imapy[$y + 1] - $imapy[$y]);
                }
            }
        }

        $ans %= 1_000_000_007;
        return (int)$ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний