850. Rectangle Area II
Task text is translated from Russian for the selected interface language. Code is left unchanged.
Вам дан двумерный array прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
return общую площадь. Поскольку ответ может быть слишком большим, return его по модулю 10^9 + 7.
Example:
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# solution
matched/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++ solution
auto-draft, review before submit#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 solution
matched/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 solution
matched/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 solution
matched/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
Active vacancies with overlapping task tags are shown.
There are no active vacancies yet.