Rumah >pembangunan bahagian belakang >tutorial php >. Kalendar Saya II
731. Kalendar II Saya
Kesukaran: Sederhana
Topik: Tatasusunan, Carian Perduaan, Reka Bentuk, Pokok Segmen, Jumlah Awalan, Set Tertib
Anda sedang melaksanakan program untuk digunakan sebagai kalendar anda. Kami boleh menambah acara baharu jika menambah acara tidak akan menyebabkan tempahan tiga kali ganda.
tempahan tiga kali berlaku apabila tiga acara mempunyai beberapa persimpangan yang tidak kosong (iaitu, beberapa saat adalah perkara biasa bagi ketiga-tiga acara itu.).
Acara ini boleh diwakili sebagai sepasang integer bermula dan berakhir yang mewakili tempahan pada selang separuh terbuka [mula, tamat), julat nombor nyata x seperti mula <= x < tamat.
Laksanakan kelas MyCalendarTwo:
Contoh 1:
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
[null, true, true, true, false, true, true]
MyCalendarTwo myCalendarTwo = new MyCalendarTwo(); myCalendarTwo.book(10, 20); // return True, The event can be booked. myCalendarTwo.book(50, 60); // return True, The event can be booked. myCalendarTwo.book(10, 40); // return True, The event can be double booked. myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking. myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked. myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
Kekangan:
Petunjuk:
Penyelesaian:
Kami perlu mengekalkan dua senarai tempahan:
Apabila acara baharu diminta, kami perlu menyemak sama ada ia akan menyebabkan tempahan tiga kali ganda. Untuk melakukannya:
Akhir sekali, jika acara melepasi kedua-dua semakan, kami menambahkannya pada senarai tempahan tunggal.
Mari laksanakan penyelesaian ini dalam PHP: 731. Kalendar II Saya
book($start, $end); */ // Example Usage $calendar = new MyCalendarTwo(); echo $calendar->book(10, 20) ? 'true' : 'false'; // true echo "\n"; echo $calendar->book(50, 60) ? 'true' : 'false'; // true echo "\n"; echo $calendar->book(10, 40) ? 'true' : 'false'; // true echo "\n"; echo $calendar->book(5, 15) ? 'true' : 'false'; // false echo "\n"; echo $calendar->book(5, 10) ? 'true' : 'false'; // true echo "\n"; echo $calendar->book(25, 55) ? 'true' : 'false'; // true echo "\n"; ?>Penjelasan:
Pembina (__construct): Memulakan objek kalendar dengan dua tatasusunan kosong untuk menyimpan tempahan tunggal dan tempahan berganda.
Fungsi Buku (buku):
- Fungsi mengambil permulaan dan akhir acara.
- Ia mula-mula menyemak sama ada acara itu bertindih dengan sebarang selang waktu dalam senarai Tempahan berganda. Jika ia berlaku, fungsi itu mengembalikan palsu kerana ia akan menghasilkan tempahan tiga kali ganda.
- Jika tiada tempahan tiga kali ganda, ia menyemak pertindihan dengan acara dalam senarai Tempahan tunggal. Sebarang pertindihan yang ditemui ditambahkan pada senarai Tempahan berganda, kerana ia kini mewakili tempahan berganda.
- Akhir sekali, acara itu ditambahkan pada senarai Tempahan tunggal dan fungsi itu kembali benar.
Kerumitan Masa:
Penyelesaian ini cekap mengendalikan sehingga 1000 panggilan ke fungsi buku seperti yang diperlukan oleh kekangan masalah.
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
Atas ialah kandungan terperinci . Kalendar Saya II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!