Meeting Rooms II
Kamu mendapatkan list rapat dalam bentuk dua array: rapat i berlangsung dari starts[i] hingga ends[i]. Satu ruangan hanya dapat menampung satu rapat pada satu waktu, dan rapat dapat dimulai di suatu ruangan tepat saat rapat lain di ruangan tersebut berakhir.
Tulis fungsi bernama minMeetingRooms yang mengembalikan jumlah ruangan terkecil yang dapat menampung semua rapat.
Fungsi
- startsinteger-array
- waktu mulai setiap rapat
- endsinteger-array
- waktu berakhirnya setiap rapat, pada indeks yang sama dengan waktu mulainya
- Mengembalikaninteger
- jumlah ruang paling sedikit yang dapat menampung semua rapat
Batasan
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- Pertemuan tidak diurutkan. Dua pertemuan mungkin identik.
Contoh
- Input
- starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
- Output
- 3
- Penjelasan
- Pada waktu 4, rapat dari 1 sampai 5, dari 2 sampai 6, dan dari 4 sampai 8 semuanya berlangsung, jadi kamu membutuhkan setidaknya
3ruangan. Tiga ruangan sudah cukup: rapat dari 7 sampai 9 menggunakan ruangan yang kosong pada waktu 5.
- Input
- starts = [12, 10, 14]ends = [14, 12, 16]
- Output
- 1
- Penjelasan
- Rapat berlangsung dari pukul 10 hingga 12, dari pukul 12 hingga 14, dan dari pukul 14 hingga 16. Masing-masing dimulai tepat saat rapat sebelumnya berakhir, jadi satu ruangan cukup untuk ketiganya.
- Input
- starts = [0, 2, 3]ends = [10, 3, 5]
- Output
- 2
- Penjelasan
- Rapat dari 0 hingga 10 menggunakan satu ruangan sepanjang waktu. Rapat dari 2 hingga 3 dan dari 3 hingga 5 berbagi ruangan kedua, jadi
2ruangan sudah cukup.
Pertanyaan lanjutan
Bisakah kamu juga menyebutkan ruangan untuk setiap rapat, dengan jumlah ruangan tidak lebih dari jawaban tersebut?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Pada setiap saat, setiap rapat yang sedang berlangsung membutuhkan ruangannya sendiri. Apa yang ditunjukkan oleh momen tersibuk dalam sehari tentang jawabannya?
Telusuri rapat berdasarkan urutan waktu mulainya. Saat rapat dimulai, satu-satunya ruangan yang perlu diperiksa adalah ruangan yang paling awal tersedia.
Simpan waktu selesai setiap ruangan dalam min-heap. Jika waktu selesai terkecil sama dengan atau lebih awal dari waktu mulai berikutnya, ruangan itu kosong: ganti waktu selesai tersebut dengan waktu selesai rapat baru. Jika tidak, tambahkan waktu selesai baru. Ukuran heap adalah jawabannya.
Solusi
Kamu membutuhkan jumlah ruangan sebanyak jumlah maksimum rapat yang berlangsung pada saat yang sama. Menghitung rapat yang berlangsung pada setiap waktu mulai membutuhkan O(n²). Pengurutan memungkinkan kamu menelusuri hari satu kali, menggunakan min-heap berisi waktu ruangan kembali tersedia atau dua list terurut berisi waktu mulai dan selesai, dalam O(n log n).
Hitung jumlah rapat yang berlangsung pada setiap waktu mulai
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Jumlah rapat yang sedang berlangsung hanya bertambah saat sebuah rapat dimulai, jadi momen tersibuk terjadi pada waktu mulai salah satu rapat. Untuk setiap rapat i, hitung rapat j yang memenuhi starts[j] ≤ starts[i] < ends[j]. Rapat yang berakhir tepat pada starts[i] tidak dihitung: ruangannya sudah kosong lagi. Pada contoh pertama, pada waktu 4 ada tiga rapat yang sedang berlangsung dan pada waktu 7 ada dua, jadi jawabannya adalah 3.
Setiap satu dari n rapat memeriksa semua n rapat: n = 5000 berarti 25 juta pemeriksaan.
Algoritma
- Untuk setiap pertemuan
i, aturrunningke0. - Untuk setiap pertemuan
j, tambahkan 1 kerunningketikastarts[j] ≤ starts[i] < ends[j]. - Simpan nilai terbesar
runningyang telah kamu temukan. - Kembalikan nilai terbesar tersebut.
def minMeetingRooms(starts, ends):
n = len(starts)
most = 0
for i in range(n):
# how many meetings are running at the moment meeting i starts
running = 0
for j in range(n):
if starts[j] <= starts[i] < ends[j]:
running += 1
most = max(most, running)
return mostMin-heap untuk waktu ruangan kembali tersedia
Intuisi
Urutkan rapat berdasarkan waktu mulai, lalu perhatikan hanya ruangan yang paling awal tersedia. Jika ruangan itu masih digunakan saat rapat dimulai, berarti semua ruangan masih digunakan, jadi kamu membuka ruangan baru. Jika ruangan itu tersedia, ruangan kosong mana pun sama baiknya: rapat yang belum dimulai memiliki waktu mulai yang tidak lebih awal, jadi ruangan yang tersedia sekarang akan tetap tersedia untuk semuanya.
Min-heap menyimpan satu waktu selesai untuk setiap ruangan dan memberikan waktu terkecil kepadamu. Pada contoh pertama, setelah diurutkan berdasarkan waktu mulai, heap bertambah hingga [5, 6, 8]. Rapat dari 7 hingga 9 menemukan 5 yang sama dengan atau lebih kecil dari 7, lalu menggantinya, sehingga tersisa [6, 8, 9]: tiga ruangan. Pengurutan membutuhkan O(n log n) dan setiap rapat melakukan satu operasi heap dengan biaya O(log n).
Algoritma
- Urutkan rapat berdasarkan waktu mulai, dengan mempertahankan setiap waktu mulai bersama waktu berakhirnya.
- Untuk setiap rapat, jika heap tidak kosong dan waktu berakhir terkecilnya sama dengan atau sebelum waktu mulai rapat, ganti waktu berakhir tersebut dengan waktu berakhir rapat.
- Jika tidak, masukkan waktu berakhir rapat: sebuah ruangan baru dibuka.
- Kembalikan ukuran heap, satu entri untuk setiap ruangan.
import heapq
def minMeetingRooms(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
free_at = [] # a min-heap: when each room's last meeting ends
for start, end in meetings:
if free_at and free_at[0] <= start:
heapq.heapreplace(free_at, end) # the earliest free room is free now: reuse it
else:
heapq.heappush(free_at, end) # every room is busy: open a new one
return len(free_at)Urutkan waktu mulai dan waktu selesai secara terpisah
Intuisi
Jawabannya adalah jumlah, jadi di setiap waktu mulai, kamu hanya perlu tahu apakah ada rapat yang sudah berakhir saat itu, bukan rapat yang mana. Urutkan waktu mulai dan waktu berakhir sebagai dua list terpisah, lalu telusuri waktu mulai dengan pointer ended pada waktu berakhir. Waktu mulai yang sama dengan atau setelah endTimes[ended] menggunakan ruang yang telah kosong itu; waktu mulai lainnya membuka satu ruang.
Jumlahnya tepat. Saat rooms bertambah, waktu berakhir berikutnya masih di masa depan, jadi semua rapat rooms berlangsung pada saat itu. Waktu mulai hanya tidak membuka ruang jika waktu berakhir yang sebenarnya sama dengan atau lebih awal darinya telah mengosongkan satu ruang. Pada contoh pertama, waktu mulai 1, 2, dan 4 semuanya terjadi sebelum waktu berakhir 5, jadi rooms mencapai 3, dan waktu mulai 7 menggunakan kembali ruang yang kosong pada 5. Dua operasi pengurutan membutuhkan O(n log n) dan penelusuran membutuhkan O(n).
Algoritma
- Urutkan salinan daftar waktu mulai dan salinan daftar waktu selesai.
- Atur
roomsdanendedke0. - Untuk setiap waktu mulai secara berurutan, jika waktunya sama dengan atau setelah
endTimes[ended], tambahkan 1 keended: rapat tersebut menggunakan ruangan yang sudah kosong. - Jika tidak, tambahkan 1 ke
rooms. - Kembalikan
rooms.
def minMeetingRooms(starts, ends):
start_times = sorted(starts)
end_times = sorted(ends)
rooms = 0
ended = 0 # how many meetings have ended, earliest end first
for start in start_times:
if start >= end_times[ended]:
ended += 1 # a meeting has ended by now: this one takes its room
else:
rooms += 1 # every room is busy: open a new one
return rooms
Jebakan dan kasus tepi
- Memeriksa
start > end, bukanstart ≥ end. Rapat tidak bisa menggunakan ruangan tepat saat ruangan itu tersedia kembali, dan rapat dari 10 sampai 12, 12 sampai 14, dan 14 sampai 16 membutuhkan 2 ruangan, bukan 1. - Memeriksa ruangan yang terakhir kamu buka, bukan ruangan yang paling cepat tersedia kembali. Untuk rapat dari 1 sampai 3, 2 sampai 10, dan 4 sampai 6, kamu membuka ruangan ketiga pada pukul 4, padahal ruangan pertama sudah kosong sejak pukul 3.
- Menjawab dengan jumlah rapat terbanyak yang tumpang tindih dengan satu rapat, lalu menambahkan satu. Rapat dari 0 sampai 10 tumpang tindih dengan rapat dari 2 sampai 3 dan 3 sampai 5, tetapi kedua rapat itu tidak pernah tumpang tindih, jadi 2 ruangan sudah cukup.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu Meeting Rooms II?
Solusi heap dan dua list sama-sama berjalan dalam waktu O(n log n) dan menggunakan ruang ekstra O(n). Pengurutan menjadi bagian yang paling memengaruhi; penelusuran setelahnya memerlukan biaya O(n log n) dengan heap dan O(n) dengan dua list.
Bisakah Meeting Rooms II diselesaikan dengan metode sweep line?
Ya. Ubah setiap rapat menjadi peristiwa +1 pada waktu mulai dan peristiwa -1 pada waktu selesai, urutkan peristiwanya, lalu lacak total berjalan terbesar. Jika waktunya sama, proses waktu selesai sebelum waktu mulai agar rapat yang bersinggungan menggunakan satu ruangan yang sama.
Apakah jawabannya sama dengan jumlah rapat terbanyak yang berlangsung bersamaan?
Ya. Rapat yang berlangsung pada waktu bersamaan membutuhkan ruangan yang berbeda, jadi kamu membutuhkan setidaknya sebanyak itu. Jika setiap rapat diberi ruangan yang tersedia sesuai urutan waktu mulai, jumlah ruangan yang dibutuhkan tidak akan lebih banyak, jadi jumlah rapat yang bertumpang tindih paling banyak adalah jawabannya.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def minMeetingRooms(starts, ends):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
starts = [4, 1, 7, 2] ends = [8, 5, 9, 6]
Output yang diharapkan
3