deno.land / x / masx200_leetcode_test@10.6.5 / rectangle-area-ii / index.ts
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141function area(current: Interval): bigint { return BigInt(current.right - current.left) * BigInt(current.up - current.down);}function rectangleArea(rectangles: number[][]): number { const left = Math.min(...rectangles.map((a) => a[0])); const down = Math.min(...rectangles.map((a) => a[1])); const right = Math.max(...rectangles.map((a) => a[2])); const up = Math.max(...rectangles.map((a) => a[3]));
const total = { left, right, down, up }; const root = new SegmentNode(total);
for (const [left, down, right, up] of rectangles) { change(root, { left, right, down, up }, 1n); }
return Number(root.value % BigInt(10 ** 9 + 7));}function change( node: SegmentNode, target: Interval, value: bigint,) { const current = node.interval; if ( target.up < current.down || target.right < current.left || target.down > current.up || target.left > current.right ) { return; }
if ( contains(target, current) ) { if (node.children.length === 0) { node.value = value * area(current);
return; } } else { if (node.children.length === 0) { const midx = [target.left, target.right].filter((a) => current.left < a && current.right > a )[0] ?? current.right; const midy = [target.down, target.up].filter((a) => current.down < a && current.up > a )[0] ?? current.up; const subinterval = TwoDSplit(current, midx, midy);
if (subinterval.length) { node.children = subinterval.map( (c) => new SegmentNode( c, area(c) * BigInt(node.value > 0), ), ); } } } if (node.children.length) { for (const child of node.children) { change(child, target, value); }
node.value = node.children.length ? node.children.reduce((a, n) => a + n.value, 0n) : node.value;
if ( node.value === value * area(current) || node.value === 0n ) { node.children.length = 0; } }}export function contains(target: Interval, current: Interval): boolean { return target.left <= current.left && target.down <= current.down && target.right >= current.right && target.up >= current.up;}
export function TwoDSplit( current: Interval, midx: number, midy: number,): Interval[] { const { left, right, up, down } = current;
if (left > right || down > up) return [];
if ((right - left) * (up - down) <= 1) return []; const mx = midx;
const my = midy;
const lr = [ { left: left, right: mx }, { left: mx, right: right }, ]; const du = [ { down: down, up: my }, { down: my, up: up }, ]; const result = lr .map(({ left, right }) => du.map(({ up, down }) => ({ left, right, down, up })) ) .flat(); return result.filter( ({ left, right, up, down }) => left <= right && down <= up && (right - left) * (up - down) && !(left === current.left && down === current.down && up === current.up && right === current.right), );}export class SegmentNode { constructor( public interval: Interval = new Interval(), public value: bigint = 0n, public children: SegmentNode[] = [], ) {}}export class Interval { constructor( public left = 0, public right = 0, public down = 0, public up = 0, ) {}}
export default rectangleArea;
Version Info