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

Tested only

Time O(n)Space 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.

Solution

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

Bu problemi 90 saniye içinde hangi kalıp ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?