Meeting Rooms II

Problem (yeniden ifade)

Toplantı zaman aralıkları verildiğinde, gereken minimum konferans odası sayısını bul.

Sezgi

Başlangıç ve bitişleri sırala; süpür: start oda sayısını artırır, end serbest bırakır; tepeyi izle.

Yaklaşımlar

export function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map((x) => x[0]!).sort((a, b) => a - b);
  const ends = intervals.map((x) => x[1]!).sort((a, b) => a - b);
  let i = 0, j = 0, cur = 0, peak = 0;
  while (i < starts.length) {
    if (starts[i]! < ends[j]!) {
      cur++;
      peak = Math.max(peak, cur);
      i++;
    } else {
      cur--;
      j++;
    }
  }
  return peak;
}

export function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map((x) => x[0]!).sort((a, b) => a - b);
  const ends = intervals.map((x) => x[1]!).sort((a, b) => a - b);
  let i = 0, j = 0, cur = 0, peak = 0;
  while (i < starts.length) {
    if (starts[i]! < ends[j]!) {
      cur++;
      peak = Math.max(peak, cur);
      i++;
    } else {
      cur--;
      j++;
    }
  }
  return peak;
}

Şablon bağlantısı

Aralık sweep / odalar.

Yansıma

• Başlangıç +1, bitiş −1. Aynı anda bitiş ve başlangıç: önce bitiş yoksa fazla oda sayarsın.
• Cevap sweep’teki en yüksek sayaç. İç içe üç toplantı 3 oda.
• Boş liste 0. Bitişik toplantılar oda paylaşır.