Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Hardsweep-line

Perfect Rectangle

Problem (yeniden ifade)

Eksen-hizalı dikdörtgenler [x1, y1, x2, y2]. Tek bir büyük dikdörtgeni tam kaplayıp kaplamadıklarını döndür: boşluk yok, örtüşme yok.

Sezgi

İki değişmez tam 2D süpürmenin yerini tutar. (1) Toplam alan bounding box’a eşit. (2) Her iç köşe çift sayıda paylaşılır (sette toggle → kaybolur); dört uç köşe bir kez kalır. Örtüşme veya delik birini bozar.

Yaklaşımlar

Alan + köşe paritesi

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Alan ve bounding box biriktir. Dört köşenin her birini sette toggle et. Kabul ancak alan == bbox ve set tam dört bbox köşesiyse.

Yürüyüş. [1,1]–[4,4]’ü dolduran dört dikdörtgen yalnızca o dört noktayı bırakır. Örtüşme alanı şişirir; boşluk ekstra iç köşe bırakır.

Trade-off. O(n), sıralama yok. Gerçek süpürme (x-olayında aktif y-aralıkları) da çalışır, şablona daha birebir, O(n log n). Alan taşması: 64-bit.

Çözüm

export function isRectangleCover(rectangles: number[][]): boolean {
  let area = 0;
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  const corners = new Set<string>();
  const toggle = (x: number, y: number) => {
    const k = `${x},${y}`;
    if (corners.has(k)) corners.delete(k);
    else corners.add(k);
  };
  for (const r of rectangles) {
    const x1 = r[0]!, y1 = r[1]!, x2 = r[2]!, y2 = r[3]!;
    area += (x2 - x1) * (y2 - y1);
    minX = Math.min(minX, x1); minY = Math.min(minY, y1);
    maxX = Math.max(maxX, x2); maxY = Math.max(maxY, y2);
    toggle(x1, y1); toggle(x1, y2); toggle(x2, y1); toggle(x2, y2);
  }
  if (area !== (maxX - minX) * (maxY - minY)) return false;
  if (corners.size !== 4) return false;
  return (
    corners.has(`${minX},${minY}`) &&
    corners.has(`${minX},${maxY}`) &&
    corners.has(`${maxX},${minY}`) &&
    corners.has(`${maxX},${maxY}`)
  );
}

export function isRectangleCover(rectangles: number[][]): boolean {
  let area = 0;
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  const corners = new Set<string>();
  const toggle = (x: number, y: number) => {
    const k = `${x},${y}`;
    if (corners.has(k)) corners.delete(k);
    else corners.add(k);
  };
  for (const r of rectangles) {
    const x1 = r[0]!, y1 = r[1]!, x2 = r[2]!, y2 = r[3]!;
    area += (x2 - x1) * (y2 - y1);
    minX = Math.min(minX, x1); minY = Math.min(minY, y1);
    maxX = Math.max(maxX, x2); maxY = Math.max(maxY, y2);
    toggle(x1, y1); toggle(x1, y2); toggle(x2, y1); toggle(x2, y2);
  }
  if (area !== (maxX - minX) * (maxY - minY)) return false;
  if (corners.size !== 4) return false;
  return (
    corners.has(`${minX},${minY}`) &&
    corners.has(`${minX},${maxY}`) &&
    corners.has(`${maxX},${minY}`) &&
    corners.has(`${maxX},${maxY}`)
  );
}

Şablon bağlantısı

Sweep Line’ın perfect-rectangle şekli: alan kontrolü artı çift-tek köşe sayımı, “her yerde örtü tam 1”in ayrık hali. LC 218 max yükseklik izler; bu tam örtüyü izler.

Yansıma

Alan toplamı sınır kutusuna eşit olmalı. Köşeler sette bir girip bir çıkmalı. Sonda sette tam dört dış köşe kalmalı.
Yalnızca alan deliği kaçırır. Yalnızca köşe, örtüşen fazla alanı kaçırır.
Tek dikdörtgen true. Örtüşen iki parça false. İç köşe çift sayıda görünür ve sette kalmaz.