Wawancara Koding: Ruang Rapat Minimum

Deskripsi dan kasus penggunaan

Anda diberikan sebuah larik tak terurut intervals. Setiap elemen adalah interval waktu integer [start, end): start bersifat inklusif dan end bersifat eksklusif. Oleh karena itu, rapat yang selesai pada waktu t akan mengosongkan ruangannya untuk rapat lain yang dimulai pada t. Asumsikan 0 <= intervals.length <= 100000 dan 0 <= start < end <= 1000000000. Kembalikan jumlah minimum ruangan yang diperlukan untuk menjadwalkan semua rapat.

Sebagai contoh, [[0, 30], [5, 10], [15, 20]] mengembalikan 2; [[1, 5], [5, 8]] mengembalikan 1; larik kosong mengembalikan 0. Ini adalah batasan wawancara yang diadopsi oleh artikel ini, bukan batasan tersembunyi yang diatribusikan ke platform mana pun.

Materi publik menyediakan beberapa jenis bukti representatif. PracHub memperbarui soal yang sama pada tahun 2026. interviewing.io menyajikan ruang rapat minimum sebagai masalah interval yang dapat diselesaikan dengan garis waktu atau antrean prioritas. Satu catatan wawancara publik dari Februari 2026 mencatat pertanyaan lanjutan seputar two pointers, antrean prioritas, dan larik untuk domain waktu terbatas. Catatan algoritma UMass memberikan bukti partisi interval utama: ketika interval diproses berdasarkan waktu mulai, jumlah ruang yang digunakan oleh algoritma greedy sama dengan kedalaman tumpang tindih maksimum. Satu akun hanya membuktikan pengalaman kandidat tersebut, sehingga artikel ini tidak menyimpulkan frekuensi wawancara secara umum maupun menetapkan pertanyaan ini ke bank soal tetap milik satu perusahaan tertentu.

Kriteria evaluasi pewawancara

Sinyal pertama adalah pemodelan. Ini adalah masalah penghitungan sumber daya, bukan penggabungan interval dan bukan pemilihan subset kompatibel terbesar. Jumlah ruang minimum sama dengan jumlah puncak rapat yang berlangsung pada saat yang sama, sering disebut sebagai kedalaman himpunan interval.

Sinyal kedua adalah semantik titik akhir. Dengan interval setengah terbuka, peristiwa selesai harus diproses sebelum peristiwa mulai pada waktu yang sama. Memperlakukan start === end sebagai tumpang tindih akan salah menetapkan dua ruang untuk [1, 5) dan [5, 8).

Sinyal ketiga adalah invarian dan pembuktian. Setelah waktu mulai dan selesai diurutkan secara terpisah, penunjuk (pointer) tidak lagi mempertahankan informasi mengenai waktu selesai mana yang menjadi milik rapat tertentu. Seorang kandidat harus menjelaskan mengapa identitas tidak relevan jika yang penting hanyalah okupansi bersamaan: cukup mengetahui apakah peristiwa berikutnya adalah waktu mulai atau waktu selesai paling awal yang tersisa.

Terakhir, pewawancara dapat menguji pilihan struktur data saat kebutuhan berubah. Pemindaian dua larik mengembalikan jumlahnya secara langsung. Permintaan untuk penetapan ruang konkret, ruang yang digunakan oleh setiap rapat, atau riwayat penggunaan kembali memerlukan min-heap yang menyimpan waktu selesai dan pengidentifikasi ruang.

Pertanyaan klarifikasi sebelum menjawab

• Apakah interval berupa [start, end) atau tertutup? Masalah ini menggunakan interval setengah terbuka, sehingga titik akhir yang bernilai sama tidak mengalami konflik.
• Apakah rapat dengan durasi nol valid? Kontrak ini memerlukan start < end dan menolak [t, t). Jika suatu bisnis mengizinkannya, tentukan apakah rapat tersebut menghabiskan sumber daya.
• Apa yang harus dikembalikan jika masukan kosong? Kembalikan 0, menghindari kesalahan inisialisasi rapat pertama.
• Apakah kita hanya mengembalikan hitungan atau juga penetapan ruang? Dua larik cukup untuk sekadar menghitung; penetapan ruang harus mempertahankan identitas rapat dan ruang yang dapat digunakan kembali.
• Bolehkah implementasi memutasi masukan? Implementasi di bawah ini menyalin nilai mulai dan selesai serta membiarkan larik pemanggil tidak berubah.
• Apakah waktu berupa safe integer? Batas atas yang dinyatakan berada dalam rentang safe-integer JavaScript. Stempel waktu yang lebih besar memerlukan kontrak representasi baru.
• Bisakah masukannya tidak valid? Masukan wawancara biasanya memenuhi kontrak. Validasi produksi seharusnya berada di batas sistem alih-alih di dalam algoritma inti.

Kerangka jawaban 30 detik

“Pertama-tama saya akan mengonfirmasi bahwa intervalnya setengah terbuka, sehingga ruang yang dikosongkan pada waktu tertentu dapat langsung digunakan kembali. Jika hanya hitungan minimum yang diperlukan, saya mengurutkan waktu mulai dan selesai secara terpisah lalu memindainya dengan dua pointer. Jika waktu mulai berikutnya secara ketat lebih awal daripada waktu selesai paling awal, saya menambah okupansi; jika tidak, saya mengosongkan ruang terlebih dahulu. Saya mencatat puncak okupansi.

Puncak tersebut merupakan batas bawah sekaligus dapat dicapai: rapat yang berlangsung simultan memerlukan ruang yang berbeda, dan pemrosesan berdasarkan waktu mulai hanya membuka ruang baru jika setiap ruang yang ada masih terisi. Pengurutan membuat waktu total menjadi O(n log n) dengan ruang ekstra O(n). Jika ada tindak lanjut yang meminta penetapan konkret, saya akan menggunakan min-heap yang berisi waktu selesai dan pengidentifikasi ruang.”

Solusi langkah demi langkah

Langkah 1: Hitung puncak okupansi dari dua aliran peristiwa yang terurut

Masukkan setiap waktu mulai ke dalam starts secara menaik dan setiap waktu selesai ke dalam ends secara menaik. startIndex menunjuk ke peristiwa mulai berikutnya yang belum diproses, sedangkan endIndex menunjuk ke peristiwa selesai berikutnya yang belum diproses. roomsInUse adalah jumlah ruang yang masih terisi tepat setelah posisi sweep saat ini. Interval yang valid memenuhi start < end, sehingga sweep tidak pernah memproses waktu selesai ketika tidak ada rapat yang aktif.

Jika starts[startIndex] < ends[endIndex], peristiwa berikutnya adalah waktu mulai: tingkatkan okupansi dan perbarui puncaknya. Jika tidak, proses waktu selesai terlebih dahulu dan kosongkan satu ruang. Perbandingan lebih kecil secara ketat dilakukan secara sengaja. Titik akhir yang bernilai sama akan mengambil cabang pengosongan ruang sebelum waktu mulai berikutnya, yang menerapkan [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
}

Mari telusuri [[0, 30], [5, 10], [15, 20]]. Waktu mulai adalah 0, 5, 15; waktu selesai adalah 10, 20, 30. Waktu mulai pada 0 dan 5 menaikkan okupansi dari 0 ke 2. Waktu selesai pada 10 mengosongkan ruang, menguranginya menjadi 1. Waktu mulai pada 15 menaikkannya kembali ke 2. Puncaknya adalah 2.

Langkah 2: Buktikan bahwa puncaknya adalah nilai optimum

Pertama, hitungan sweep ini benar. Representasikan setiap [start, end) sebagai peristiwa mulai +1 dan peristiwa selesai -1, urutkan berdasarkan waktu, dan proses peristiwa selesai sebelum mulai jika terjadi kesamaan waktu. Setelah peristiwa apa pun, jumlah berjalan sama dengan jumlah interval yang masih mencakup garis waktu tepat setelahnya, yang tepat merupakan jumlah ruang yang sedang terisi. Menggabungkan dua larik terurut dengan pointer melintasi semua peristiwa dalam urutan tersebut.

Selanjutnya, buktikan bahwa puncaknya optimal. Misalkan kedalaman tumpang tindih maksimum adalah d. Pada suatu saat tertentu, terdapat d rapat yang berjalan secara bersamaan, sehingga setiap jadwal memerlukan setidaknya d ruang; ini adalah batas bawah. Ketika rapat diproses berdasarkan waktu mulai, penetapan greedy membuka ruang baru hanya jika semua ruang yang ada sedang terisi oleh rapat yang belum selesai. Jika algoritma membuka ruang k, rapat baru dan k - 1 rapat lainnya berjalan bersamaan pada saat itu, sehingga k <= d. Oleh karena itu, jadwal yang hanya menggunakan d ruang dapat diwujudkan. Batas atas yang layak sama dengan batas bawah, sehingga nilai minimumnya adalah d, tepat sebesar nilai puncak yang dikembalikan oleh sweep.

Membangun larik membutuhkan biaya O(n), dua pengurutan berbiaya O(n log n), dan pemindaian gabungan berbiaya O(n). Total waktu adalah O(n log n) dengan ruang ekstra O(n). Jika waktu berasal dari domain diskret yang kecil dan tetap, difference array dapat menggantikan ini menjadi waktu O(n + U) dan ruang O(U). Optimasi tersebut tidak cocok ketika batas waktunya mencapai satu miliar.

Langkah 3: Pilih heap atau difference array saat persyaratan berubah

Solusi lain adalah mengurutkan rapat berdasarkan waktu mulai dan menyimpan waktu selesai setiap ruang yang terisi dalam min-heap. Sebelum memproses suatu rapat, keluarkan (pop) setiap entri dengan end <= start, lalu masukkan (push) waktu selesai yang baru. Ukuran puncak heap adalah jawabannya. Cara ini juga membutuhkan waktu O(n log n) dan ruang kasus terburuk O(n).

Untuk sekadar menghitung, sweep lebih ringkas dan memperjelas aturan bahwa waktu selesai mendahului waktu mulai yang bernilai sama. Heap bernilai untuk ekstensi kebutuhan: ubah setiap entri dari end menjadi { end, roomId }. Pertahankan min-heap kedua untuk pengidentifikasi ruang yang tersedia, ambil kembali pengidentifikasi setelah rapat selesai, dan petakan setiap indeks rapat asli ke ruang konkret. Jika persyaratannya menentukan untuk memilih ruang tersedia bernomor terkecil, memilih hanya berdasarkan waktu selesai paling awal tidaklah cukup; ruang terisi dan ruang tersedia harus dikelola secara terpisah.

Pemesanan online dinamis adalah masalah yang berbeda. Ketika rapat mendatang tiba satu per satu dan mungkin dibatalkan, mengurutkan ulang setiap interval secara berulang bisa menjadi terlalu mahal. Beban kerja kueri mungkin memerlukan penyimpan peristiwa terurut, interval tree, atau indeks kalender. Jawaban larik luring O(n log n) tidak boleh disajikan sebagai desain sistem online yang lengkap.

Contoh jawaban berkualitas tinggi

“Saya akan menyelesaikan ini di bawah kondisi [start, end), sehingga ruang dapat digunakan kembali ketika satu waktu selesai sama dengan waktu mulai lainnya. Pemeriksaan konflik berpasangan adalah garis dasar yang valid tetapi berbiaya O(n^2) dalam kasus terburuk. Dengan hingga 100.000 rapat, saya akan mengurutkan peristiwanya.

Saya membuat larik mulai dan selesai yang terurut. Dua pointer menentukan peristiwa berikutnya: waktu mulai yang lebih awal menambah okupansi saat ini dan memperbarui nilai maksimum; waktu selesai yang lebih awal atau bernilai sama akan mengurangi okupansi terlebih dahulu. Untuk [[0, 30], [5, 10], [15, 20]], okupansi berubah melalui 1, 2, 1, dan 2, sehingga jawabannya adalah 2.

Kebenaran memiliki dua bagian. Hitungan sweep yang berjalan sama dengan jumlah interval aktif, sehingga nilai maksimumnya adalah kedalaman tumpang tindih d. Setiap jadwal membutuhkan setidaknya d ruang ketika rapat-rapat tersebut berlangsung bersamaan. Penetapan greedy berdasarkan waktu mulai hanya menambah ruang saat semua ruang yang ada sedang terisi, sehingga tidak pernah menggunakan lebih dari d. Algoritma ini optimal. Kompleksitasnya membutuhkan waktu O(n log n) dan ruang O(n). Jika saya memerlukan pengidentifikasi ruang setiap rapat, saya akan mempertahankan indeks asli dan menetapkan ruang menggunakan heap waktu selesai ditambah heap pengidentifikasi yang tersedia.”

Kesalahan umum

• Kesalahan: Menyelesaikan penggabungan interval (interval merging). Mengapa gagal: Jumlah interval yang digabungkan tidak menentukan puncak okupansi bersamaan. Perbaikan: Sweep peristiwa mulai dan selesai lalu catat puncak hitungan aktif.
• Kesalahan: Memproses waktu mulai sebelum selesai pada titik akhir yang bernilai sama. Mengapa gagal: Ruang yang dapat langsung digunakan kembali akan dihitung dua kali. Perbaikan: Berikan prioritas pada peristiwa selesai berdasarkan kontrak setengah terbuka.
• Kesalahan: Menggunakan pengurutan bawaan JavaScript. Mengapa gagal: Pengurutan leksikografis menempatkan 10 sebelum 2. Perbaikan: Berikan (a, b) => a - b secara eksplisit.
• Kesalahan: Mengembalikan roomsInUse akhir. Mengapa gagal: Okupansi akhir bisa lebih rendah daripada puncak sebelumnya. Perbaikan: Perbarui maximumRooms pada setiap waktu mulai.
• Kesalahan: Membandingkan setiap pasangan rapat. Mengapa gagal: Waktu kasus terburuk menjadi O(n^2). Perbaikan: Urutkan dan gabungkan kedua aliran peristiwa secara linear.
• Kesalahan: Hanya melakukan pop pada satu rapat yang selesai saat menghasilkan penetapan. Mengapa gagal: Himpunan aktif dan himpunan tersedia menjadi tidak lengkap. Perbaikan: Keluarkan setiap ruang dengan end <= start dan kelola pengidentifikasi yang dapat digunakan kembali secara terpisah.
• Kesalahan: Membiarkan batas interval tidak terdefinisi. Mengapa gagal: Pengujian akan berbeda hasil pada titik akhir yang bernilai sama. Perbaikan: Tentukan interval setengah terbuka atau tertutup serta prioritas peristiwa bersamaan sebelum menulis kode.
• Kesalahan: Menambahkan atribusi perusahaan dari label bank soal publik. Mengapa gagal: Tag pihak ketiga dan catatan satu kandidat tidak membuktikan kepemilikan tetap. Perbaikan: Pertahankan companyName sebagai null jika buktinya tidak cukup dan nyatakan hanya apa yang didukung oleh masing-masing sumber.

Pertanyaan lanjutan dan tanggapan

Mengapa dua larik terurut boleh membuang korespondensi antarrapat?

Tujuannya hanya bergantung pada jumlah rapat aktif pada setiap saat. Perubahan hitungan berikutnya ditentukan oleh waktu mulai paling awal yang belum diproses dan waktu selesai paling awal yang belum diproses, terlepas dari rapat mana yang memiliki waktu selesai tersebut. Korespondensi menjadi diperlukan kembali untuk penetapan ruang atau pelacakan per rapat, sehingga gunakan heap yang berisi indeks rapat dan pengidentifikasi ruang untuk persyaratan tersebut.

Apa yang berubah untuk interval tertutup [start, end]?

Waktu selesai dan waktu mulai pada waktu yang sama mengalami konflik. Perbandingan harus memproses waktu mulai terlebih dahulu, meningkatkan okupansi saat start <= end. Penjelasan yang lebih aman adalah dengan mendefinisikan prioritas kesamaan waktu secara eksplisit daripada sekadar mengubah operator secara mekanis.

Bagaimana cara mengembalikan pengidentifikasi ruang untuk setiap rapat?

Pertahankan indeks asli dan urutkan berdasarkan waktu mulai. Simpan ruang yang terisi dalam min-heap dari { end, roomId }. Sebelum setiap rapat, pindahkan setiap ruang dengan end <= start ke dalam min-heap pengidentifikasi yang tersedia. Gunakan kembali pengidentifikasi terkecil yang tersedia atau buat yang baru, lalu catat assignment[originalIndex] = roomId.

Mengapa jumlah ruang minimum sama dengan tumpang tindih maksimum?

Tumpang tindih maksimum adalah batas bawah yang tidak dapat dihindari karena rapat yang berlangsung bersamaan tidak dapat berbagi ruangan. Algoritma greedy berdasarkan waktu mulai hanya membuka ruang ketika setiap ruang yang ada masih terisi. Oleh karena itu, setiap ruang yang dibukanya berhubungan dengan jumlah rapat yang tumpang tindih pada saat itu, sehingga tidak pernah melebihi batas bawah. Kesamaan ini membuktikan optimalitas.

Kasus batas mana saja yang harus diuji?

Minimal, uji larik kosong, satu interval, tidak ada tumpang tindih, tumpang tindih penuh, rangkaian titik akhir yang bernilai sama, waktu mulai yang identik, waktu selesai yang identik, interval duplikat, masukan yang terurut terbalik, dan data acak mendekati batas ukuran. Solusi pembanding (oracle) berbasis O(n^2) kecil atau discrete-event dapat mendukung pengujian diferensial acak, tetapi kode verifikasi sekali pakai tidak boleh dicampur ke dalam implementasi produksi.

Bisakah domain waktu yang kecil menghasilkan solusi waktu linear?

Bisa. Gunakan difference array dengan ukuran yang sebanding dengan domain waktu U, tambahkan satu pada setiap waktu mulai, kurangi satu pada setiap waktu selesai, dan ambil jumlah prefiks puncaknya. Kompleksitasnya adalah waktu O(n + U) dan ruang O(U). Cara ini bermanfaat hanya jika U kecil dan memori terkendali; pengurutan lebih aman di bawah batas satu miliar saat ini.