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

Data Stream as Disjoint Intervals

Problem (yeniden ifade)

Tamsayı akışı. Her addNum(val) sonrası getIntervals(): eklenen her değeri örten ayrık kapalı aralıklar, sıralı, değen veya örtüşenler birleşmiş.

Sezgi

Mevcut ayrık listeyi sıralı tut. Yeni nokta yoz aralık [val, val]. Mevcut aralıkları süpür: kesin soldakiler kalsın, örtüşen veya değenler (b >= val-1 ve a <= val+1) birleşsin, kesin sağdakiler ondan sonra kalsın.

Yaklaşımlar

Ekle ve birleştir

Doğrulanmadı

Zaman O(n) add / O(n) getAlan O(n)

Fikir. Sıralı listede bir geçiş. b < val-1 → kopyala. a > val+1 → yeni aralığı bir kez yaz, sonra kopyala. Değilse [val,val]’i [a,b]’yi kapayacak şekilde genişlet. En sağdaysa sona ekle.

Yürüyüş. 1, 3, 7 → [[1,1],[3,3],[7,7]]. 2 ekle → [1,3]. 6 ekle → [6,7].

Trade-off. Benzersiz sayısı küçükken doğrusal tarama yeter. Dengeli ağaç O(log n) ekleme; mülakat taramayı kabul eder. Değmek birleşmedir ([1,1] ve [2,2] → [1,2]).

Çözüm

export class SummaryRanges {
  private ivs: number[][] = [];

  addNum(val: number): void {
    const n = [val, val];
    const res: number[][] = [];
    let placed = false;
    for (const iv of this.ivs) {
      const a = iv[0]!, b = iv[1]!;
      if (b < n[0]! - 1) res.push([a, b]);
      else if (a > n[1]! + 1) {
        if (!placed) { res.push(n); placed = true; }
        res.push([a, b]);
      } else {
        n[0] = Math.min(n[0]!, a);
        n[1] = Math.max(n[1]!, b);
      }
    }
    if (!placed) res.push(n);
    this.ivs = res;
  }

  getIntervals(): number[][] {
    return this.ivs;
  }
}

export class SummaryRanges {
  private ivs: number[][] = [];

  addNum(val: number): void {
    const n = [val, val];
    const res: number[][] = [];
    let placed = false;
    for (const iv of this.ivs) {
      const a = iv[0]!, b = iv[1]!;
      if (b < n[0]! - 1) res.push([a, b]);
      else if (a > n[1]! + 1) {
        if (!placed) { res.push(n); placed = true; }
        res.push([a, b]);
      } else {
        n[0] = Math.min(n[0]!, a);
        n[1] = Math.max(n[1]!, b);
      }
    }
    if (!placed) res.push(n);
    this.ivs = res;
  }

  getIntervals(): number[][] {
    return this.ivs;
  }
}

Şablon bağlantısı

Sweep Line’ın data-stream şekli: her ekleme, aktif ayrık kümeye birleşen bir olay. LC 56 ile aynı birleşme kuralı, çevrimiçi.

Yansıma

Yeni nokta [val, val]. b < val-1 ise eski aralık durur. a > val+1 ise nokta araya girer.
Değilse temas veya örtüşme: [min(a,val), max(b,val)]. İki komşu birden yutulabilir.
Aynı sayı iki kez aralığı büyütmez. Boş akış tek nokta üretir.