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

Mediumdifference-array

Corporate Flight Bookings

Problem (yeniden ifade)

1..n numaralı n uçuş. Rezervasyonlar [first, last, seats] kapsayıcı aralıkta koltuk ayırır. Her uçuş için koltuk sayısını döndür.

Sezgi

Klasik difference array: first-1 konumunda +seats, last konumunda -seats, sonra önek toplam.

Yaklaşımlar

Difference array

Doğrulanmadı

Zaman O(n + m)Alan O(n)

Fikir. diff[l-1]+=s; r n’den küçükse: diff[r]-=s; önek ile yeniden kur.

Yürüyüş. n=5, bookings=[[1,2,10],[2,3,20],[2,5,25]] → [10,55,45,25,25].

Trade-off. Çevrimdışı aralık eklemeleri için segment tree abartı.

Çözüm

export function corpFlightBookings(bookings: number[][], n: number): number[] {
  const diff = new Array(n).fill(0);
  for (const [f, l, s] of bookings) {
    diff[f! - 1]! += s!;
    if (l! < n) diff[l!]! -= s!;
  }
  for (let i = 1; i < n; i++) diff[i]! += diff[i - 1]!;
  return diff;
}

export function corpFlightBookings(bookings: number[][], n: number): number[] {
  const diff = new Array(n).fill(0);
  for (const [f, l, s] of bookings) {
    diff[f! - 1]! += s!;
    if (l! < n) diff[l!]! -= s!;
  }
  for (let i = 1; i < n; i++) diff[i]! += diff[i - 1]!;
  return diff;
}

Şablon bağlantısı

Çok sayıda aralık güncellemesi için difference-array şablonu.

Yansıma

last dahil. diff[last+1] -= seats neden last değil?
Uçuşlar 1’den başlar. Cevabı 1..n dilimlemek hangi bir-kaymayı yakalar?
Rezervasyon yoksa n tane 0. Üst üste binen koltuklar prefix’te toplanmalı.