Meeting Rooms

Q: Apa kompleksitas waktu Meeting Rooms?

Mengurutkan rapat berdasarkan waktu mulai membutuhkan biaya O(n log n) , dan penelusuran yang membandingkan elemen bertetangga membutuhkan biaya O(n) , jadi totalnya O(n log n) . Membandingkan setiap pasangan membutuhkan biaya O(n²) .

Q: Apakah rapat yang bersinggungan dihitung sebagai tumpang tindih?

Tidak dalam masalah ini: sebuah rapat boleh dimulai tepat saat rapat lain berakhir, jadi pemeriksaannya menggunakan start < previous end yang ketat. Jika rapat yang waktunya bersentuhan tidak diperbolehkan, kondisinya akan menjadi start ≤ previous end .

Q: Bagaimana cara mencari jumlah minimum ruang rapat?

Urutkan waktu mulai dan waktu selesai sebagai dua list terpisah, lalu telusuri keduanya: setiap waktu mulai membuka satu ruangan, dan setiap waktu selesai yang sama dengan atau sebelum waktu mulai berikutnya membebaskan satu ruangan. Jumlah ruangan terbanyak yang terbuka secara bersamaan adalah jawabannya. Soal ini menanyakan apakah satu ruangan cukup.

MudahInterval Pengurutan

+10

Kamu mendapatkan daftar rapat dalam bentuk dua array: rapat i berlangsung dari starts[i] hingga ends[i]. Seseorang ingin menghadiri semuanya, jadi tidak boleh ada dua rapat yang waktunya tumpang tindih. Sebuah rapat boleh dimulai tepat saat rapat lainnya berakhir. Kembalikan true jika orang tersebut dapat menghadiri setiap rapat, dan false jika tidak.

Fungsi

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

startsinteger-array: waktu mulai setiap rapat
endsinteger-array: waktu berakhirnya setiap rapat, pada indeks yang sama dengan waktu mulainya
Mengembalikanboolean: benar jika tidak ada dua pertemuan yang tumpang tindih, salah jika tidak

Batasan

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Pertemuan tidak diurutkan. Dua pertemuan mungkin identik.

Contoh

Input: starts = [9, 13, 10]ends = [10, 15, 12]
Output: true
Penjelasan: Urutan waktu pertemuannya adalah dari 9 sampai 10, 10 sampai 12, dan 13 sampai 15. Pertemuan kedua dimulai tepat saat pertemuan pertama berakhir, dan itu diperbolehkan, jadi jawabannya adalah true.

Input: starts = [1, 4, 7]ends = [5, 6, 8]
Output: false
Penjelasan: Pertemuan dari 1 sampai 5 masih berlangsung pada pukul 4, saat pertemuan dari 4 sampai 6 dimulai, jadi jawabannya adalah false.

Pertanyaan lanjutan

Jika rapat dipesan satu per satu, bagaimana kamu akan memeriksa setiap pemesanan baru terhadap jadwal dalam O(log n), tanpa mengurutkan semuanya lagi?

Solusi

Memeriksa setiap pasangan rapat akan menemukan setiap bentrok dalam O(n²). Urutkan berdasarkan waktu mulai: setelah itu, rapat hanya dapat berbenturan dengan rapat di sebelahnya dalam urutan yang sudah diurutkan, jadi satu perbandingan per rapat sudah cukup.

Bandingkan setiap pasangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Dua rapat bertabrakan jika masing-masing dimulai sebelum rapat lainnya berakhir: untuk 1 sampai 5 dan 4 sampai 6, 1 sebelum 6 dan 4 sebelum 5. Operator < yang ketat pada kedua sisi membuat rentang 9 sampai 10 dan 10 sampai 12 bersentuhan tanpa bertabrakan. Uji setiap pasangan dan kembalikan false saat menemukan tabrakan pertama.

Dengan n = 5000, ada sekitar 12,5 juta pasangan, dan jadwal tanpa tabrakan membuat kamu harus memeriksa semuanya.

Algoritma

Untuk setiap indeks i, dan setiap indeks j setelahnya:
Jika starts[i] < ends[j] dan starts[j] < ends[i], kedua pertemuan bertumpang tindih: kembalikan false.
Jika tidak ada pasangan yang bertumpang tindih, kembalikan true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Urutkan berdasarkan awal dan periksa elemen di sebelahnya

Intuisi

Urutkan rapat berdasarkan waktu mulai, dengan tetap memasangkan setiap waktu mulai dengan waktu selesai masing-masing. Jika sejauh ini belum ditemukan bentrokan, rapat-rapat tersebut membentuk rantai, masing-masing mulai pada atau setelah waktu selesai rapat sebelumnya. Jadi, rapat yang tepat sebelum rapat baru berakhir paling akhir, dan rapat baru yang mulai pada atau setelah waktu berakhirnya tidak bertumpang tindih dengan rapat mana pun. Rapat yang mulai sebelum waktu itu akan berbenturan.

Waktu mulai yang sama selalu berbenturan, karena setiap rapat berlangsung setidaknya satu satuan waktu, dan pemeriksaan yang sama akan mendeteksinya. Pengurutan memerlukan O(n log n), penelusuran memerlukan O(n), dan salinan pasangan rapat memerlukan ruang O(n).

Algoritma

Pasangkan setiap waktu mulai dengan waktu akhirnya.
Urutkan pasangan berdasarkan waktu mulai.
Untuk setiap rapat setelah rapat pertama, bandingkan waktu mulainya dengan waktu akhir rapat sebelumnya.
Jika waktu mulainya lebih kecil, kembalikan false.
Setelah perulangan, kembalikan true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Jebakan dan kasus tepi

Mengurutkan starts dan membiarkan ends tetap dalam urutan input. Setiap waktu selesai harus tetap bersama waktu mulainya sendiri, atau kamu akan membandingkan waktu mulai dengan waktu selesai dari pertemuan lain.
Menggunakan ≤ alih-alih <. Pertemuan dari pukul 9 sampai 10 dan dari pukul 10 sampai 12 hanya bersentuhan, dan jawabannya adalah true.
Membandingkan waktu yang bersebelahan dalam urutan input. Input tidak diurutkan: pertemuan dari pukul 1 sampai 5, pukul 7 sampai 8, dan pukul 4 sampai 6 tidak bertabrakan dengan pertemuan yang bersebelahan, tetapi pertemuan pertama dan terakhir bertumpang tindih.
Menulis pengujian pasangan dengan satu kondisi, seperti starts[j] < ends[i]. Untuk pertemuan dari pukul 5 sampai 6 dan pukul 0 sampai 1, dalam urutan tersebut, 0 < 6 melaporkan tabrakan yang sebenarnya tidak terjadi.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Meeting Rooms?

Mengurutkan rapat berdasarkan waktu mulai membutuhkan biaya O(n log n), dan penelusuran yang membandingkan elemen bertetangga membutuhkan biaya O(n), jadi totalnya O(n log n). Membandingkan setiap pasangan membutuhkan biaya O(n²).

Apakah rapat yang bersinggungan dihitung sebagai tumpang tindih?

Tidak dalam masalah ini: sebuah rapat boleh dimulai tepat saat rapat lain berakhir, jadi pemeriksaannya menggunakan start < previous end yang ketat. Jika rapat yang waktunya bersentuhan tidak diperbolehkan, kondisinya akan menjadi start ≤ previous end.

Bagaimana cara mencari jumlah minimum ruang rapat?

Urutkan waktu mulai dan waktu selesai sebagai dua list terpisah, lalu telusuri keduanya: setiap waktu mulai membuka satu ruangan, dan setiap waktu selesai yang sama dengan atau sebelum waktu mulai berikutnya membebaskan satu ruangan. Jumlah ruangan terbanyak yang terbuka secara bersamaan adalah jawabannya. Soal ini menanyakan apakah satu ruangan cukup.

def canAttendMeetings(starts, ends):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

starts = [9, 13, 10]
ends = [10, 15, 12]

Output yang diharapkan

true