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

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

Fark dizisi

Tested only

Time O(n + D)Space O(D)

Fikir. diff[from]+=p; diff[to]-=p; koşan toplam doluluk.

Adım adım. trips=[[2,1,5],[3,3,7]], cap=4 → doluluk 5’e çıkar → false; cap=5 → true.

Trade-off’lar. Sırala+olay tarama eşdeğer; domain küçükken fark O(D).

Solution

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

Hangi kalıp bunu 90 saniyede ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?