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

Merge Intervals

Problem (yeniden ifade)

[start, end] aralıkları verildiğinde tüm örtüşen aralıkları birleştir ve aynı aralıkları kaplayan örtüşmesiz sonucu döndür.

Sezgi

Başlangıca göre sırala. Tara ve ya mevcut açık aralığa birleştir ya da boşluk varsa yenisini ekle.

Yaklaşımlar

Başlangıca göre sırala + birleştir

Doğrulanmadı

Zaman O(n log n)Alan O(n)

Fikir. Aralıkları start’a göre sırala. Birleştirilmiş bir liste tut. next.start ≤ last.end ise last.end = max(last.end, next.end); değilse next’i ekle.

Yürüyüş. [[1,3],[2,6],[8,10]] → ilk ikisini [1,6] olarak birleştir, sonra [8,10] ekle.

Trade-off. Sıralama baskındır. Yerinde hileler vardır ama mülakatlarda nadiren değer.

Çözüm

export function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0]! - b[0]!);
  const res: number[][] = [];
  for (const interval of intervals) {
    const last = res[res.length - 1];
    if (!last || interval[0]! > last[1]!) res.push([...interval]);
    else last[1] = Math.max(last[1]!, interval[1]!);
  }
  return res;
}

export function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0]! - b[0]!);
  const res: number[][] = [];
  for (const interval of intervals) {
    const last = res[res.length - 1];
    if (!last || interval[0]! > last[1]!) res.push([...interval]);
    else last[1] = Math.max(last[1]!, interval[1]!);
  }
  return res;
}

Şablon bağlantısı

Amiral gemisi intervals problemi. sırala sonra doğrusal birleştir.

Yansıma

Başlangıca göre sırala. Örtüşme start <= last.end. Bitişe göre sıralarsan birleşmeyenler karışır.
Bitişik start == last.end birleşir mi? İç içe aralıkta end max.
Tek aralık ve boş liste. Sıra, birleşmemiş parçaların başlangıç sırasıdır.