Car Pooling

Problem (yeniden ifade)

Yolculuklar [numPassengers, from, to]. Kapasite capacity. Kapasiteyi aşmadan herkesi alıp bırakabilir misin?

Sezgi

Doğru üzerinde aralık güncellemeleri: from’da +p, to’da -p. Önek tara; herhangi bir an capacity’yi aşarsa başarısız.

Yaklaşımlar

export function carPooling(trips: number[][], capacity: number): boolean {
  let maxTo = 0;
  for (const t of trips) maxTo = Math.max(maxTo, t[2]!);
  const diff = new Array(maxTo + 1).fill(0);
  for (const [p, f, t] of trips) {
    diff[f!]! += p!;
    diff[t!]! -= p!;
  }
  let cur = 0;
  for (const d of diff) {
    cur += d;
    if (cur > capacity) return false;
  }
  return true;
}

export function carPooling(trips: number[][], capacity: number): boolean {
  let maxTo = 0;
  for (const t of trips) maxTo = Math.max(maxTo, t[2]!);
  const diff = new Array(maxTo + 1).fill(0);
  for (const [p, f, t] of trips) {
    diff[f!]! += p!;
    diff[t!]! -= p!;
  }
  let cur = 0;
  for (const d of diff) {
    cur += d;
    if (cur > capacity) return false;
  }
  return true;
}

Şablon bağlantısı

Fark dizisi aralık güncellemeleri, sonra önek ile yeniden kurma.

Yansıma

• Yolculuk bir aralık ekleme. İniş durağı to kapasiteyi neden geri verir, to-1 değil?
• Aynı noktada inen ve binen: önce iniş mi? Kapasite tam doluyken eşitlik yasal mı?
• Konumlar 0..1000 ise fark dizisi ucuz. Seyrek duraklarda sıralı sweep mi daha doğru?