Temu Duga Pengekodan: Bilangan Minimum Bilik Mesyuarat

Keperluan dan kes penggunaan

Anda diberikan satu tatasusunan tidak terisih intervals. Setiap elemen ialah selang masa integer [start, end): start adalah inklusif dan end adalah eksklusif. Oleh itu, mesyuarat yang tamat pada masa t akan mengosongkan biliknya untuk mesyuarat lain yang bermula pada t. Andaikan 0 <= intervals.length <= 100000 dan 0 <= start < end <= 1000000000. Kembalikan bilangan bilik minimum yang diperlukan untuk menjadualkan setiap mesyuarat.

Sebagai contoh, [[0, 30], [5, 10], [15, 20]] mengembalikan 2; [[1, 5], [5, 8]] mengembalikan 1; tatasusunan kosong mengembalikan 0. Ini adalah kekangan temu duga yang diguna pakai oleh artikel ini, bukannya had tersembunyi yang dikaitkan dengan mana-mana platform.

Bahan awam menyediakan beberapa jenis bukti yang representatif. PracHub mengemas kini soalan yang sama pada tahun 2026. interviewing.io membentangkan bilik mesyuarat minimum sebagai masalah selang yang boleh diselesaikan dengan garis masa atau giliran keutamaan. Satu catatan temu duga awam dari Februari 2026 merekodkan soalan susulan mengenai dua penuding, giliran keutamaan, dan tatasusunan untuk domain masa terhad. Nota algoritma UMass menyediakan bukti pemetakan selang teras: apabila selang diproses mengikut masa mula, bilangan bilik yang digunakan oleh algoritma tamak adalah sama dengan kedalaman pertindihan maksimum. Satu catatan hanya membuktikan pengalaman calon tersebut, jadi artikel ini tidak membuat inferens kekerapan temu duga umum mahupun menetapkan soalan ini kepada bank soalan tetap satu syarikat tertentu.

Kriteria penilaian penemu duga

Isyarat pertama ialah pemodelan. Ini adalah masalah pengiraan sumber, bukan penggabungan selang dan bukan pemilihan subset serasi terbesar. Bilangan bilik minimum adalah sama dengan bilangan puncak mesyuarat yang sedang berlangsung pada bila-bila masa, sering dipanggil kedalaman set selang.

Isyarat kedua ialah semantik titik akhir. Dengan selang separuh terbuka, peristiwa tamat mesti diproses sebelum peristiwa mula pada masa yang sama. Menganggap start === end sebagai pertindihan secara salah memperuntukkan dua bilik kepada [1, 5) dan [5, 8).

Isyarat ketiga ialah invarian dan pembuktian. Sebaik sahaja masa mula dan tamat diisih secara berasingan, penuding tidak lagi mengekalkan maklumat masa tamat yang mana kepunyaan mesyuarat tertentu. Calon harus menerangkan mengapa identiti tidak relevan apabila hanya penghunian serentak yang penting: memadai untuk mengetahui sama ada peristiwa seterusnya ialah masa mula atau tamat terawal yang tinggal.

Akhir sekali, penemu duga boleh menguji pilihan struktur data di bawah perubahan keperluan. Sapuan dua tatasusunan mengembalikan kiraan secara langsung. Permintaan untuk peruntukan bilik konkrit, bilik yang digunakan oleh setiap mesyuarat, atau sejarah penggunaan semula memerlukan min-heap yang mengekalkan kedua-dua masa tamat dan pengecam bilik.

Soalan untuk dijelaskan sebelum menjawab

• Adakah selang [start, end) atau tertutup? Masalah ini menggunakan selang separuh terbuka, jadi titik akhir yang sama tidak berkonflik.
• Adakah mesyuarat dengan tempoh sifar sah? Kontrak ini memerlukan start < end dan menolak [t, t). Jika perniagaan membenarkannya, tentukan sama ada ia menggunakan sumber.
• Apakah yang patut dikembalikan oleh input kosong? Kembalikan 0, mengelakkan sebarang ralat pemulaan mesyuarat pertama.
• Adakah kita hanya mengembalikan kiraan atau juga peruntukan bilik? Dua tatasusunan mencukupi untuk kiraan; peruntukan bilik mesti mengekalkan identiti mesyuarat dan bilik yang boleh digunakan semula.
• Bolehkah pelaksanaan mengubah suai input? Pelaksanaan di bawah menyalin nilai mula dan tamat serta membiarkan tatasusunan pemanggil tidak disentuh.
• Adakah masa integer selamat? Had atas yang dinyatakan berada dalam julat integer selamat JavaScript. Cap masa yang lebih besar memerlukan kontrak perwakilan baharu.
• Bolehkah input tidak sah? Input temu duga biasanya memenuhi kontrak. Pengesahan pengeluaran sepatutnya berada pada sempadan sistem dan bukannya di dalam algoritma teras.

Rangka kerja jawapan 30 saat

“Saya akan mengesahkan terlebih dahulu bahawa selang masa adalah separuh terbuka, jadi bilik yang dikosongkan pada masa tertentu boleh digunakan semula serta-merta. Apabila hanya kiraan minimum diperlukan, saya mengisih masa mula dan tamat secara berasingan dan mengimbasnya dengan dua penuding. Jika masa mula seterusnya adalah lebih awal daripada masa tamat terawal, saya meningkatkan penghunian; jika tidak, saya mengosongkan bilik terlebih dahulu. Saya mengekalkan puncak penghunian.

Puncak tersebut merupakan had bawah dan boleh dicapai: mesyuarat serentak memerlukan bilik yang berbeza, dan pemprosesan mengikut masa mula hanya membuka bilik baharu apabila setiap bilik sedia ada masih dihuni. Pengisihan menjadikan jumlah masa O(n log n) dengan ruang tambahan O(n). Jika susulan meminta peruntukan konkrit, saya akan menggunakan min-heap yang mengandungi masa tamat dan pengecam bilik.”

Penyelesaian langkah demi langkah

Langkah 1: Kira puncak penghunian daripada dua aliran peristiwa yang diisih

Letakkan setiap masa mula ke dalam starts mengikut tertib menaik dan setiap masa tamat ke dalam ends mengikut tertib menaik. startIndex menunjuk kepada peristiwa mula seterusnya yang belum diproses, manakala endIndex menunjuk kepada peristiwa tamat seterusnya yang belum diproses. roomsInUse ialah bilangan bilik yang masih dihuni sejurus selepas kedudukan sapuan semasa. Selang yang sah memenuhi start < end, jadi sapuan tidak pernah memproses masa tamat semasa tiada mesyuarat aktif.

Jika starts[startIndex] < ends[endIndex], peristiwa seterusnya ialah mula: tingkatkan penghunian dan kemas kini nilai puncak. Jika tidak, proses masa tamat dahulu dan lepaskan satu bilik. Perbandingan kurang daripada yang ketat adalah disengajakan. Titik akhir yang sama mengambil cabang pelepasan sebelum masa mula seterusnya, melaksanakan [start, end) dengan tepat.

export function minimumMeetingRooms(
  intervals: ReadonlyArray<readonly [number, number]>,
): number {
  if (intervals.length === 0) return 0

  const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
  const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)

  let startIndex = 0
  let endIndex = 0
  let roomsInUse = 0
  let maximumRooms = 0

  while (startIndex < intervals.length) {
    if (starts[startIndex] < ends[endIndex]) {
      roomsInUse += 1
      maximumRooms = Math.max(maximumRooms, roomsInUse)
      startIndex += 1
    } else {
      roomsInUse -= 1
      endIndex += 1
    }
  }

  return maximumRooms
}

Jejaki [[0, 30], [5, 10], [15, 20]]. Masa mula ialah 0, 5, 15; masa tamat ialah 10, 20, 30. Masa mula pada 0 dan 5 meningkatkan penghunian daripada 0 kepada 2. Masa tamat pada 10 melepaskan bilik, mengurangkannya kepada 1. Masa mula pada 15 meningkatkannya kepada 2 semula. Puncaknya ialah 2.

Langkah 2: Buktikan bahawa puncak adalah optimum

Pertama, kiraan sapuan adalah betul. Wakili setiap [start, end) sebagai peristiwa mula +1 dan peristiwa tamat -1, isih mengikut masa, dan proses peristiwa tamat sebelum mula sekiranya terikat. Selepas sebarang peristiwa, jumlah berjalan adalah sama dengan bilangan selang yang masih meliputi garis masa sejurus selepas itu, iaitu tepat bilangan bilik yang dihuni. Penggabungan dua tatasusunan yang diisih dengan penuding merentasi semua peristiwa dalam tertib tersebut.

Seterusnya, buktikan bahawa puncak adalah optimum. Biarkan kedalaman pertindihan maksimum menjadi d. Pada satu-satu masa, d mesyuarat berjalan serentak, jadi setiap jadual memerlukan sekurang-kurangnya d bilik; ini adalah had bawah. Apabila mesyuarat diproses mengikut masa mula, peruntukan tamak membuka bilik baharu hanya jika semua bilik sedia ada dihuni oleh mesyuarat yang belum tamat. Jika ia membuka bilik k, mesyuarat baharu dan k - 1 yang lain wujud bersama pada masa itu, jadi k <= d. Oleh itu, jadual yang hanya menggunakan d bilik wujud. Had atas yang boleh dilaksanakan adalah sama dengan had bawah, jadi minimumnya ialah d, tepat pada puncak yang dikembalikan oleh sapuan.

Membina tatasusunan memerlukan kos O(n), dua pengisihan memerlukan kos O(n log n), dan imbasan cantuman memerlukan kos O(n). Jumlah masa ialah O(n log n) dengan ruang tambahan O(n). Jika masa datang daripada domain diskret yang kecil dan tetap, tatasusunan perbezaan (difference array) boleh menukarnya kepada masa O(n + U) dan ruang O(U). Pengoptimuman itu tidak sesuai apabila had masa adalah satu bilion.

Langkah 3: Pilih heap atau tatasusunan perbezaan apabila keperluan berubah

Penyelesaian lain mengisih mesyuarat mengikut masa mula dan menyimpan masa tamat setiap bilik yang dihuni dalam min-heap. Sebelum memproses mesyuarat, keluarkan (pop) setiap entri dengan end <= start, kemudian masukkan (push) masa tamat yang baharu. Saiz puncak heap ialah jawapannya. Ini juga mengambil masa O(n log n) dan ruang kes terburuk O(n).

Untuk kiraan sahaja, sapuan lebih pendek dan mendedahkan peraturan bahawa masa tamat mendahului masa mula yang terikat. Heap sangat berharga untuk lanjutan: tukar setiap entri daripada end kepada { end, roomId }. Kekalkan min-heap kedua bagi pengecam bilik yang tersedia, tebus guna pengecam selepas mesyuarat tamat, dan petakan setiap indeks mesyuarat asal kepada bilik konkrit. Jika keperluan menyatakan untuk memilih bilik tersedia bernombor paling rendah, memilih hanya mengikut masa tamat terawal adalah tidak mencukupi; bilik yang dihuni dan tersedia mesti diuruskan secara berasingan.

Tempahan dalam talian dinamik ialah masalah yang berbeza. Apabila mesyuarat masa hadapan tiba secara individu dan mungkin dibatalkan, mengisih setiap selang berulang kali mungkin terlalu mahal. Beban kerja pertanyaan mungkin memerlukan stor peristiwa teratur, interval tree, atau indeks kalendar. Jawapan tatasusunan luar talian O(n log n) tidak boleh dibentangkan sebagai reka bentuk sistem dalam talian yang lengkap.

Contoh jawapan berkualiti tinggi

“Saya akan menyelesaikan ini di bawah syarat [start, end), jadi bilik boleh digunakan semula apabila satu masa tamat bersamaan dengan masa mula yang lain. Pemeriksaan konflik berpasangan ialah garis dasar yang sah tetapi berkos O(n^2) dalam kes terburuk. Dengan sehingga 100,000 mesyuarat, saya akan mengisih peristiwa tersebut.

Saya mencipta tatasusunan mula dan tamat yang diisih. Dua penuding menentukan peristiwa seterusnya: masa mula yang lebih awal menambah penghunian semasa dan mengemas kini maksimum; masa tamat yang lebih awal atau terikat mengurangkan penghunian terlebih dahulu. Untuk [[0, 30], [5, 10], [15, 20]], penghunian berubah melalui 1, 2, 1, dan 2, jadi jawapannya ialah 2.

Ketepatan mempunyai dua bahagian. Kiraan sapuan berjalan adalah sama dengan bilangan selang aktif, jadi maksimumnya ialah kedalaman pertindihan d. Setiap jadual memerlukan sekurang-kurangnya d bilik apabila mesyuarat tersebut wujud bersama. Peruntukan tamak mengikut masa mula menambah bilik hanya semasa semua bilik sedia ada dihuni, jadi ia tidak pernah menggunakan lebih daripada d. Algoritma ini adalah optimum. Ia mengambil masa O(n log n) dan ruang O(n). Jika saya memerlukan pengecam bilik untuk setiap mesyuarat, saya akan mengekalkan indeks asal dan memperuntukkan bilik dengan heap masa tamat ditambah heap pengecam yang tersedia.”

Kesilapan biasa

• Kesilapan: Menyelesaikan penggabungan selang (interval merging). Sebab ia gagal: Bilangan selang yang digabungkan tidak menentukan puncak penghunian serentak. Pembetulan: Sapu peristiwa mula dan tamat serta kekalkan puncak kiraan aktif.
• Kesilapan: Memproses masa mula sebelum tamat pada titik akhir yang sama. Sebab ia gagal: Bilik yang boleh digunakan semula serta-merta dikira dua kali. Pembetulan: Berikan keutamaan kepada peristiwa tamat di bawah kontrak separuh terbuka.
• Kesilapan: Menggunakan isihan lalai JavaScript. Sebab ia gagal: Susunan leksikografi meletakkan 10 sebelum 2. Pembetulan: Hantarkan (a, b) => a - b secara eksplisit.
• Kesilapan: Mengembalikan roomsInUse akhir. Sebab ia gagal: Penghunian akhir boleh menjadi lebih rendah daripada puncak sebelumnya. Pembetulan: Kemas kini maximumRooms pada setiap masa mula.
• Kesilapan: Membandingkan setiap pasangan mesyuarat. Sebab ia gagal: Masa kes terburuk menjadi O(n^2). Pembetulan: Isih dan gabungkan kedua-dua aliran peristiwa secara linear.
• Kesilapan: Mengeluarkan (pop) hanya satu mesyuarat yang selesai semasa menghasilkan peruntukan bilik. Sebab ia gagal: Set aktif dan tersedia menjadi tidak lengkap. Pembetulan: Keluarkan setiap bilik dengan end <= start dan uruskan pengecam yang boleh digunakan semula secara berasingan.
• Kesilapan: Membiarkan sempadan selang tidak ditakrifkan. Sebab ia gagal: Ujian akan tidak sehaluan pada titik akhir yang sama. Pembetulan: Tentukan selang separuh terbuka atau tertutup dan keutamaan peristiwa terikat sebelum mengekod.
• Kesilapan: Menambah atribusi syarikat daripada label bank soalan awam. Sebab ia gagal: Tag pihak ketiga dan satu catatan calon tidak membuktikan pemilikan tetap. Pembetulan: Kekalkan companyName sebagai null apabila bukti tidak mencukupi dan nyatakan hanya perkara yang disokong oleh setiap sumber.

Soalan susulan dan respons

Mengapakah dua tatasusunan yang diisih boleh membuang kesepadanan mesyuarat?

Objektif hanya bergantung pada kiraan mesyuarat aktif pada setiap masa. Perubahan kiraan seterusnya ditentukan oleh masa mula terawal yang belum diproses dan masa tamat terawal yang belum diproses, tanpa mengira mesyuarat mana yang memiliki masa tamat tersebut. Kesepadanan menjadi perlu semula untuk peruntukan bilik atau penjejakan bagi setiap mesyuarat, jadi gunakan heap yang mengandungi indeks mesyuarat dan pengecam bilik untuk keperluan tersebut.

Apakah yang berubah untuk selang tertutup [start, end]?

Masa tamat dan masa mula pada masa yang sama adalah berkonflik. Perbandingan mesti memproses masa mula terlebih dahulu, meningkatkan penghunian apabila start <= end. Penjelasan yang lebih selamat adalah dengan menentukan keutamaan ikatan secara eksplisit dan bukannya menukar pengendali secara mekanikal.

Bagaimanakah anda mengembalikan pengecam bilik untuk setiap mesyuarat?

Kekalkan indeks asal dan isih mengikut masa mula. Simpan bilik yang dihuni dalam min-heap { end, roomId }. Sebelum setiap mesyuarat, alihkan setiap bilik dengan end <= start ke dalam min-heap pengecam yang tersedia. Gunakan semula pengecam tersedia terkecil atau cipta yang baharu, kemudian rekodkan assignment[originalIndex] = roomId.

Mengapakah bilangan bilik minimum sama dengan pertindihan maksimum?

Pertindihan maksimum ialah had bawah yang tidak dapat dielakkan kerana mesyuarat serentak tidak boleh berkongsi bilik. Algoritma tamak mengikut masa mula membuka bilik hanya apabila setiap bilik sedia ada masih dihuni. Oleh itu, setiap bilik yang dibukanya sepadan dengan bilangan mesyuarat yang bertindih pada masa itu, jadi ia tidak pernah melebihi had bawah. Persamaan ini membuktikan keoptimuman.

Kes pinggir manakah yang perlu diuji?

Sekurang-kurangnya, uji tatasusunan kosong, satu selang, tiada pertindihan, pertindihan lengkap, rantaian titik akhir yang sama, masa mula yang serupa, masa tamat yang serupa, selang pendua, input yang diisih secara terbalik, dan data rawak berhampiran had saiz. Oracle berasaskan O(n^2) kecil atau peristiwa diskret boleh menyokong ujian pembezaan rawak, tetapi kod pengesahan sekali sahaja tidak boleh dicampur ke dalam pelaksanaan pengeluaran.

Bolehkah domain masa yang kecil menghasilkan penyelesaian masa linear?

Boleh. Gunakan tatasusunan perbezaan dengan saiz yang berkadar dengan domain masa U, tambah satu pada setiap masa mula, tolak satu pada setiap masa tamat, dan ambil jumlah awalan puncak. Kerumitannya ialah masa O(n + U) dan ruang O(U). Ia berbaloi hanya apabila U adalah kecil dan memori terkawal; pengisihan adalah lebih selamat di bawah had satu bilion semasa.