. 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:

• MyCalendarTwo() Memulakan objek kalendar.
• boolean book(int start, int end) Mengembalikan benar jika acara boleh ditambahkan pada kalendar dengan jayanya tanpa menyebabkan tempahan tiga kali ganda. Jika tidak, kembali palsu dan jangan tambahkan acara pada kalendar.

Contoh 1:

• Input:

  ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
  [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

• Output:

  [null, true, true, true, false, true, true]

• Penjelasan:

  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:

• 0 <= mula < tamat <= 10⁹
• Maksimum 1000 panggilan akan dibuat untuk menempah.

Petunjuk:

1. Simpan dua senarai selang yang diisih: satu senarai adalah sepanjang masa yang sekurang-kurangnya sekali ditempah, dan senarai lain adalah sepanjang masa yang pastinya dua kali ditempah. Jika tiada tempahan berganda bercanggah, maka tempahan akan berjaya dan anda harus mengemas kini tempahan tunggal dan berganda anda dengan sewajarnya.

Penyelesaian:

Kami perlu mengekalkan dua senarai tempahan:

1. Tempahan Tunggal: Senarai yang menjejaki semua acara yang ditempah sekali.
2. Tempahan Berganda: Senarai yang menjejaki semua acara yang ditempah dua kali.

Apabila acara baharu diminta, kami perlu menyemak sama ada ia akan menyebabkan tempahan tiga kali ganda. Untuk melakukannya:

• Kami mula-mula menyemak sama ada acara baharu itu bertindih dengan mana-mana selang dalam senarai tempahan berganda. Jika ya, kami tidak boleh menambah acara kerana ia akan membawa kepada tempahan tiga kali ganda.
• Jika tiada pertindihan dengan tempahan berganda, kami kemudian menyemak senarai tempahan tunggal dan menambah pertindihan acara baharu dengan acara sedia ada pada tempahan berganda senarai.

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:



Kerumitan masa adalah lebih kurang O(n) untuk setiap operasi tempahan, dengan n ialah bilangan tempahan yang dibuat setakat ini. Ini kerana bagi setiap tempahan, kami mungkin perlu menyemak semua tempahan sebelumnya dalam senarai Tempahan tunggal dan Tempahan berganda.


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:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Kalendar Saya II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!