Sweep Line

Nasıl düşünülür

Sweep line, 2D aralık problemini 1D olay dizisine çevirir. X ekseni boyunca soldan sağa süpürülen dikey bir çizgi hayal et. Her aralık iki olaya katkıda bulunur: başlangıçta giriş, bitişte çıkış. Tüm olayları koordinata göre sırala, sırayla işle, girişte aralığı aktif sete ekle; çıkışta çıkar. “x’te kaç aralık aktif?” veya “x’te maksimum yükseklik ne?” sorusunun cevabı her olay noktasındaki aktif setin bir fonksiyonudur.

Aynı koordinattaki olaylar arasındaki sıralama önemli: aralıklar uç noktası paylaşıyorsa “bitiş” “başlangıç”tan önce mi (örtüşme yok) sonra mı (örtüşme var) gelmeli? Bunu problem başına açıkça tanımla. Silüetlerde girişte yüksekliğe göre azalan, çıkışta artan sırala ki aktif setin max’ı doğru güncellensin.

Şablon şekilleri

Şekil	Temel hamle	Örnek
Toplantı odaları II	Giriş +1, çıkış -1; maks aktif say	LC 253
Silüet	Aktif yükseklik seti; max değişince yayınla	LC 218
Veri akışı aralıkları	Olayda ekle/birleştir; BST veya sıralı liste	LC 352
Mükemmel dikdörtgen	Alan toplamı + sweep ile örtüşme kontrolü	LC 391

Karmaşıklık temeli

O(n log n) zaman (olay sıralama), O(n) alan (aktif set). Her olay bir kez işlenir; aktif set genelde heap veya sıralı yapıdır.

Şablondan probleme

1. Her aralık/dikdörtgeni giriş ve çıkış olaylarına ayır.
2. Olayları koordinata göre sırala; problemin örtüşme kuralına uyan sıralamayı seç.
3. Olayları sırayla işle: aktif seti ve güncel cevabı koru.
4. Cevabı aktif setten çıkar, maks sayı, maks yükseklik veya birleştirilmiş liste.

/** Sweep line template: max concurrent intervals (meeting rooms II). */

export function minMeetingRooms(intervals: [number, number][]): number {
  const events: [number, number][] = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);
    events.push([end, -1]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]!);
  let active = 0, max = 0;
  for (const [, delta] of events) {
    active += delta;
    if (active > max) max = active;
  }
  return max;
}

/** Sweep line template: max concurrent intervals (meeting rooms II). */

export function minMeetingRooms(intervals: [number, number][]): number {
  const events: [number, number][] = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);
    events.push([end, -1]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]!);
  let active = 0, max = 0;
  for (const [, delta] of events) {
    active += delta;
    if (active > max) max = active;
  }
  return max;
}