850. Rectangle Area II
O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.
Вам дан двумерный array прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
return общую площадь. Поскольку ответ может быть слишком большим, return его по модулю 10^9 + 7.
Exemplo:
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# solução
correspondente/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++ solução
rascunho 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 solução
correspondente/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 solução
correspondente/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 solução
correspondente/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.
😎
Vacancies for this task
vagas ativas with overlapping task tags are mostradas.
Ainda não há vagas ativas.