850. Rectangle Area II
Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[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.
C# решение
сопоставлено/оригиналpublic class Solution {
public int RectangleArea(int[][] rectangles) {
int N = rectangles.Length;
HashSet<int> Xvals = new HashSet<int>();
HashSet<int> Yvals = new HashSet<int>();
foreach (var rec in rectangles) {
Xvals.Add(rec[0]);
Xvals.Add(rec[2]);
Yvals.Add(rec[1]);
Yvals.Add(rec[3]);
}
int[] imapx = Xvals.ToArray();
Array.Sort(imapx);
int[] imapy = Yvals.ToArray();
Array.Sort(imapy);
Dictionary<int, int> mapx = new Dictionary<int, int>();
Dictionary<int, int> mapy = new Dictionary<int, int>();
for (int i = 0; i < imapx.Length; ++i)
mapx[imapx[i]] = i;
for (int i = 0; i < imapy.Length; ++i)
mapy[imapy[i]] = i;
bool[,] grid = new bool[imapx.Length, imapy.Length];
foreach (var rec in rectangles)
for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
grid[x, y] = true;
long ans = 0;
for (int x = 0; x < grid.GetLength(0); ++x)
for (int y = 0; y < grid.GetLength(1); ++y)
if (grid[x, y])
ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);
ans %= 1_000_000_007;
return (int)ans;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int RectangleArea(int[][] rectangles) {
int N = rectangles.size();
HashSet<int> Xvals = new HashSet<int>();
HashSet<int> Yvals = new HashSet<int>();
foreach (var rec in rectangles) {
Xvals.push_back(rec[0]);
Xvals.push_back(rec[2]);
Yvals.push_back(rec[1]);
Yvals.push_back(rec[3]);
}
vector<int>& imapx = Xvals.ToArray();
sort(imapx.begin(), imapx.end());
vector<int>& imapy = Yvals.ToArray();
sort(imapy.begin(), imapy.end());
unordered_map<int, int> mapx = new unordered_map<int, int>();
unordered_map<int, int> mapy = new unordered_map<int, int>();
for (int i = 0; i < imapx.size(); ++i)
mapx[imapx[i]] = i;
for (int i = 0; i < imapy.size(); ++i)
mapy[imapy[i]] = i;
bool[,] grid = new bool[imapx.size(), imapy.size()];
foreach (var rec in rectangles)
for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
grid[x, y] = true;
long ans = 0;
for (int x = 0; x < grid.GetLength(0); ++x)
for (int y = 0; y < grid.GetLength(1); ++y)
if (grid[x, y])
ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);
ans %= 1_000_000_007;
return (int)ans;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int rectangleArea(int[][] rectangles) {
int N = rectangles.length;
Set<Integer> Xvals = new HashSet();
Set<Integer> Yvals = new HashSet();
for (int[] rec: rectangles) {
Xvals.add(rec[0]);
Xvals.add(rec[2]);
Yvals.add(rec[1]);
Yvals.add(rec[3]);
}
Integer[] imapx = Xvals.toArray(new Integer[0]);
Arrays.sort(imapx);
Integer[] imapy = Yvals.toArray(new Integer[0]);
Arrays.sort(imapy);
Map<Integer, Integer> mapx = new HashMap();
Map<Integer, Integer> mapy = new HashMap();
for (int i = 0; i < imapx.length; ++i)
mapx.put(imapx[i], i);
for (int i = 0; i < imapy.length; ++i)
mapy.put(imapy[i], i);
boolean[][] grid = new boolean[imapx.length][imapy.length];
for (int[] rec: rectangles)
for (int x = mapx.get(rec[0]); x < mapx.get(rec[2]); ++x)
for (int y = mapy.get(rec[1]); y < mapy.get(rec[3]); ++y)
grid[x][y] = true;
long ans = 0;
for (int x = 0; x < grid.length; ++x)
for (int y = 0; y < grid[0].length; ++y)
if (grid[x][y])
ans += (long) (imapx[x+1] - imapx[x]) * (imapy[y+1] - imapy[y]);
ans %= 1_000_000_007;
return (int) ans;
}
}JavaScript решение
сопоставлено/оригиналvar rectangleArea = function(rectangles) {
let N = rectangles.length;
let Xvals = new Set(), Yvals = new Set();
for (let rec of rectangles) {
Xvals.add(rec[0]);
Xvals.add(rec[2]);
Yvals.add(rec[1]);
Yvals.add(rec[3]);
}
let imapx = Array.from(Xvals).sort((a, b) => a - b);
let imapy = Array.from(Yvals).sort((a, b) => a - b);
let mapx = new Map(), mapy = new Map();
imapx.forEach((v, i) => mapx.set(v, i));
imapy.forEach((v, i) => mapy.set(v, i));
let grid = Array.from({ length: imapx.length }, () => Array(imapy.length).fill(false));
for (let rec of rectangles) {
for (let x = mapx.get(rec[0]); x < mapx.get(rec[2]); x++) {
for (let y = mapy.get(rec[1]); y < mapy.get(rec[3]); y++) {
grid[x][y] = true;
}
}
}
let ans = 0;
for (let x = 0; x < grid.length; x++) {
for (let y = 0; y < grid[0].length; y++) {
if (grid[x][y]) {
ans += (imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);
}
}
}
ans %= 1_000_000_007;
return ans;
};Go решение
сопоставлено/оригиналimport (
"sort"
)
func rectangleArea(rectangles [][]int) int {
const MOD int = 1_000_000_007
Xvals := make(map[int]struct{})
Yvals := make(map[int]struct{})
for _, rec := range rectangles {
Xvals[rec[0]] = struct{}{}
Xvals[rec[2]] = struct{}{}
Yvals[rec[1]] = struct{}{}
Yvals[rec[3]] = struct{}{}
}
var imapx []int
for x := range Xvals {
imapx = append(imapx, x)
}
sort.Ints(imapx)
var imapy []int
for y := range Yvals {
imapy = append(imapy, y)
}
sort.Ints(imapy)
mapx := make(map[int]int)
for i, x := range imapx {
mapx[x] = i
}
mapy := make(map[int]int)
for i, y := range imapy {
mapy[y] = i
}
grid := make([][]bool, len(imapx))
for i := range grid {
grid[i] = make([]bool, len(imapy))
}
for _, rec := range rectangles {
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 := int64(0)
for x := 0; x < len(grid); x++ {
for y := 0; y < len(grid[0]); y++ {
if grid[x][y] {
ans += int64(imapx[x+1]-imapx[x]) * int64(imapy[y+1]-imapy[y])
}
}
}
ans %= MOD
return int(ans)
}Algorithm
Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.
Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.
Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.