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

Mediumsweep-line

Remove Interval

Problem (yeniden ifade)

Sıralı, ayrık yarı-açık aralıklar [start, end) ve çıkarılacak bir aralık toBeRemoved = [a, b). Kalan parçaları, hâlâ sıralı ve ayrık, döndür.

Sezgi

Her girdi aralığı bağımsızdır (örtüşmezler). [a, b) karşısında ya bütün kalır (örtüşme yok), ya kaybolur (tam kaplanmış), ya da sol [s, a) ve/veya sağ [b, e) artıklarına bölünür.

Yaklaşımlar

Her aralığı kırp

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. [s, e) için: e ≤ a veya s ≥ b ise tut. Değilse s < a iken [s, a), e > b iken [b, e) yaz.

Yürüyüş. [[0,2],[3,4],[5,7]] eksi [1,6] → [0,1] ve [6,7]. [[0,5]] eksi [2,3] → [0,2],[3,5].

Trade-off. Girdi zaten sıralı ve ayrık olduğu için doğrusal. Uçlar yarı-açık, e == a örtüşmez. Boş artıkları (s == a veya e == b) katı eşitsizlikler atlar.

Çözüm

export function removeInterval(intervals: number[][], toBeRemoved: number[]): number[][] {
  const a = toBeRemoved[0]!, b = toBeRemoved[1]!;
  const res: number[][] = [];
  for (const iv of intervals) {
    const s = iv[0]!, e = iv[1]!;
    if (e <= a || s >= b) res.push([s, e]);
    else {
      if (s < a) res.push([s, a]);
      if (e > b) res.push([b, e]);
    }
  }
  return res;
}

export function removeInterval(intervals: number[][], toBeRemoved: number[]): number[][] {
  const a = toBeRemoved[0]!, b = toBeRemoved[1]!;
  const res: number[][] = [];
  for (const iv of intervals) {
    const s = iv[0]!, e = iv[1]!;
    if (e <= a || s >= b) res.push([s, e]);
    else {
      if (s < a) res.push([s, a]);
      if (e > b) res.push([b, e]);
    }
  }
  return res;
}

Şablon bağlantısı

Tek-aralık süpürme: silinecek aralık tek “aktif” olay, her girdi aralığı ona göre kırpılır. Skyline’da bir çıkış olayının delik açmasıyla aynı sol-artık / sağ-artık bölünmesi.

Yansıma

Aralıklar [s, e). Tamamen solda veya tamamen sağda olan durur. Örtüşen ortadan kesilir.
s < a ise [s, a) kalır. e > b ise [b, e) kalır. İkisi birden olursa aralık ikiye bölünür.
Tam örtüşen düşer. e == a örtüşmez; aralık durur. Çıktı sırayı korur.