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 greedy

Non-overlapping Intervals

Problem (yeniden ifade)

Aralıklar verildiğinde, kalanların örtüşmemesi için silinecek minimum sayıda aralığı döndür. Uç noktalar değebilir (end == next.start sorun değil).

Sezgi

Tutulan aralıkları maksimize etmek klasik activity selection: daha sonrakilere yer kalsın diye her zaman en erken biten aralığı tut. Silinenler = n - kept.

Yaklaşımlar

Bitişe göre sırala + greedy tut

Doğrulanmadı

Zaman O(n log n)Alan O(1) or O(n)

Fikir. Bitişe göre artan sırala. keptEnd izle. Sonraki keptEnd’den önce başlarsa at (sayı +1); yoksa tut ve keptEnd’i güncelle.

Yürüyüş. [[1,2],[2,3],[3,4],[1,3]] → bitişe göre sırala: [1,2],[1,3],[2,3],[3,4]. [1,2] tut, [1,3] at, [2,3] tut, [3,4] tut → 1 silme.

Trade-off. Başlangıca göre sıralayıp her zaman daha geç biteni atmak eşdeğer ama biraz daha fazla muhasebe. Sıralı aralıklar üzerinde DP doğru ama kodlaması daha yavaş.

Çözüm

export function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals = [...intervals].sort((a, b) => a[1]! - b[1]!);
  let keptEnd = intervals[0]![1]!;
  let removals = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i]![0]! < keptEnd) removals++;
    else keptEnd = intervals[i]![1]!;
  }
  return removals;
}

export function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals = [...intervals].sort((a, b) => a[1]! - b[1]!);
  let keptEnd = intervals[0]![1]!;
  let removals = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i]![0]! < keptEnd) removals++;
    else keptEnd = intervals[i]![1]!;
  }
  return removals;
}

Şablon bağlantısı

Aralıklar üzerinde greedy çizelgeleme: sıralama anahtarı end, start değil. Merge Intervals ile karşılaştır (start’a göre sırala).

Yansıma

Bitişe göre sırala. Erken biteni tut. Başlangıca göre açgözlü neden kanıtlanmaz?
Örtüşmede silme sayacı artar, tutulan bitiş güncellenmez. Temas örtüşme değil.
Hepsi örtüşür: n−1 silme. Hiç örtüşmez: 0.