Задача: 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 {
    func rectangleArea(_ rectangles: [[Int]]) -> Int {
        let N = rectangles.count
        var Xvals = Set<Int>()
        var Yvals = Set<Int>()

        for rec in rectangles {
            Xvals.insert(rec[0])
            Xvals.insert(rec[2])
            Yvals.insert(rec[1])
            Yvals.insert(rec[3])
        }

        let imapx = Array(Xvals).sorted()
        let imapy = Array(Yvals).sorted()

        var mapx = [Int: Int]()
        var mapy = [Int: Int]()
        for i in 0..<imapx.count {
            mapx[imapx[i]] = i
        }
        for i in 0..<imapy.count {
            mapy[imapy[i]] = i
        }

        var grid = Array(repeating: Array(repeating: false, count: imapy.count), count: imapx.count)
        for rec in rectangles {
            for x in mapx[rec[0]]!..<mapx[rec[2]]! {
                for y in mapy[rec[1]]!..<mapy[rec[3]]! {
                    grid[x][y] = true
                }
            }
        }

        var ans: Int64 = 0
        for x in 0..<grid.count {
            for y in 0..<grid[0].count {
                if grid[x][y] {
                    ans += Int64(imapx[x+1] - imapx[x]) * Int64(imapy[y+1] - imapy[y])
                }
            }
        }

        ans %= 1_000_000_007
        return Int(ans)
    }
}

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