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

Mediumintervals

Insert Interval

Problem (yeniden ifade)

Örtüşmeyen ve başlangıca göre sıralı aralık listesi ile bir newInterval verilir. newInterval öyle eklenmeli ki sonuç sıralı ve örtüşmesiz kalsın (gerekirse birleştir).

Sezgi

Girdi zaten sıralı. Tek geçiş: yeniden tamamen önce gelen aralıkları kopyala, ona değen her şeyi birleştir, sonra kalanı kopyala.

Yaklaşımlar

Üç fazlı doğrusal tarama

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Faz 1: end < new.start olan aralıkları ekle. Faz 2: cur.start ≤ new.end iken new’i genişlet. Faz 3: kalanı ekle.

Adım adım. intervals = [[1,3],[6,9]], new = [2,5] → [1,5] olarak birleştir, sonra [6,9] ekle → [[1,5],[6,9]].

Ödünleşimler. Liste önceden sıralı olduğu için sıralama gerekmez. İlk örtüşme için ikili arama mümkün ama birleştirme fazının asimptotik maliyetini iyileştirmez.

Çözüm

export function insert(intervals: number[][], newInterval: number[]): number[][] {
  const res: number[][] = [];
  let i = 0;
  const n = intervals.length;
  const ni = [...newInterval];

  // intervals fully before newInterval
  while (i < n && intervals[i]![1]! < ni[0]!) {
    res.push([...intervals[i]!]);
    i++;
  }

  // merge all that overlap newInterval
  while (i < n && intervals[i]![0]! <= ni[1]!) {
    ni[0] = Math.min(ni[0]!, intervals[i]![0]!);
    ni[1] = Math.max(ni[1]!, intervals[i]![1]!);
    i++;
  }
  res.push(ni);

  // remaining intervals after the merged block
  while (i < n) {
    res.push([...intervals[i]!]);
    i++;
  }
  return res;
}

export function insert(intervals: number[][], newInterval: number[]): number[][] {
  const res: number[][] = [];
  let i = 0;
  const n = intervals.length;
  const ni = [...newInterval];

  // intervals fully before newInterval
  while (i < n && intervals[i]![1]! < ni[0]!) {
    res.push([...intervals[i]!]);
    i++;
  }

  // merge all that overlap newInterval
  while (i < n && intervals[i]![0]! <= ni[1]!) {
    ni[0] = Math.min(ni[0]!, intervals[i]![0]!);
    ni[1] = Math.max(ni[1]!, intervals[i]![1]!);
    i++;
  }
  res.push(ni);

  // remaining intervals after the merged block
  while (i < n) {
    res.push([...intervals[i]!]);
    i++;
  }
  return res;
}

Şablon bağlantısı

Insert, bilinen sıralı girdi ve tek ekstra aralıkla merge’dir. Örtüşme kuralı Merge Intervals ile aynı.

Yansıma

Üç faz: yeni aralıktan önce bitenler, örtüşenlerin birleşimi, sonra başlayanlar.
Birleşimin start’ı min, end’i max. Örtüşme yoksa araya tek parça girer.
Yeni aralık en başta, en sonda veya liste boş. Çıktı başlangıca göre sıralı kalır.