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

Check if All the Integers in a Range Are Covered

Problem (yeniden ifade)

[1,50] içindeki tamsayıları kaplayan ranges verildiğinde, [left, right] içindeki her tamsayı en az bir aralıkla kaplanıyorsa true döndür.

Sezgi

Kaplama sayılarının difference array’i; [left, right] içindeki her nokta için önek > 0.

Yaklaşımlar

Difference array ile kaplama

Doğrulanmadı

Zaman O(n + U)Alan O(U)

Fikir. start’ta +1, end+1’de -1. Koşan kaplamayla 1..50 tara.

Yürüyüş. ranges=[[1,2],[3,4],[5,6]], left=2,right=5 → true.

Trade-off. Domain çok küçük (50); aralık başına kaba döngü de yeter.

Çözüm

export function isCovered(ranges: number[][], left: number, right: number): boolean {
  const diff = Array(52).fill(0);
  for (const r of ranges) {
    diff[r[0]!]!++;
    diff[r[1]! + 1]!--;
  }
  let cur = 0;
  for (let i = 1; i <= 50; i++) {
    cur += diff[i]!;
    if (i >= left && i <= right && cur <= 0) return false;
  }
  return true;
}

export function isCovered(ranges: number[][], left: number, right: number): boolean {
  const diff = Array(52).fill(0);
  for (const r of ranges) {
    diff[r[0]!]!++;
    diff[r[1]! + 1]!--;
  }
  let cur = 0;
  for (let i = 1; i <= 50; i++) {
    cur += diff[i]!;
    if (i >= left && i <= right && cur <= 0) return false;
  }
  return true;
}

Şablon bağlantısı

Aralık kaplaması için difference array.

Yansıma

Kapsama bir fark dizisi. [left, right] içinde her sayacın ≥ 1 olması yetiyor mu, tam 1 mi?
Kesişen aralıklar sayacı 2 yapar. 0 kalan bir hücre var mı diye prefix’i nerede okursun?
left == right tek nokta. Sorgunun dışına taşan aralık cevabı değiştirmemeli.