850. Rectangle Area II
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Вам дан двумерный arreglo прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
return общую площадь. Поскольку ответ может быть слишком большим, return его по модулю 10^9 + 7.
Ejemplo:
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# solución
coincidente/originalpublic 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++ solución
borrador automático, revisar antes de enviar#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 solución
coincidente/originalclass 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 solución
coincidente/originalvar 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 solución
coincidente/originalimport (
"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.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.