. Kalendar Saya I

729. Kalendar Saya Saya

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Binari, Reka Bentuk, Pokok Segmen, Set Tertib

Anda sedang melaksanakan program untuk digunakan sebagai kalendar anda. Kami boleh menambah acara baharu jika menambah acara tidak akan menyebabkan tempahan berganda.

tempahan berganda berlaku apabila dua acara mempunyai beberapa persimpangan yang tidak kosong (iaitu, beberapa saat adalah perkara biasa bagi kedua-dua acara.).

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

Laksanakan kelas MyCalendar:

• MyCalendar() Memulakan objek kalendar.
• boolean book(int start, int end) Mengembalikan benar jika acara boleh ditambahkan pada kalendar dengan jayanya tanpa menyebabkan tempahan berganda. Jika tidak, kembalikan palsu dan jangan tambahkan acara pada kalendar.

Contoh 1:

• Input:

  ["MyCalendar", "book", "book", "book"]
  [[], [10, 20], [15, 25], [20, 30]]

• Output:

  [null, true, false, true]

• Penjelasan:

  MyCalendar myCalendar = new MyCalendar();
  myCalendar.book(10, 20); // return True
  myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
  myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Kekangan:

• 0 9
• Maksimum 1000 panggilan akan dibuat untuk menempah.

Petunjuk:

1. Simpan acara sebagai senarai selang yang diisih. Jika tiada satu pun acara bercanggah, maka acara baharu boleh ditambah.

Penyelesaian:

Kami perlu menyimpan setiap acara dan menyemak sama ada acara baharu itu bercanggah dengan mana-mana acara sedia ada sebelum menempahnya. Memandangkan paling banyak 1000 panggilan untuk menempah dibenarkan, kami boleh menyimpan acara dalam senarai dan melelang melaluinya untuk menyemak pertindihan semasa menempah acara baharu.

Pelan:

1. Menyimpan Acara: Kami akan mengekalkan senarai di mana setiap entri adalah sepasang [mula, tamat] mewakili selang masa yang ditempah.
2. Semak Konflik: Sebelum menambah acara baharu, kami akan mengulangi senarai acara yang ditempah dan menyemak sama ada acara baharu itu bercanggah dengan mana-mana acara sedia ada. Pertindihan berlaku jika masa mula acara baharu kurang daripada masa tamat acara sedia ada dan masa tamat acara baharu lebih besar daripada masa mula acara sedia ada.
3. Acara Buku: Jika tiada konflik ditemui, kami menambah acara baharu pada senarai tempahan kami.

Mari laksanakan penyelesaian ini dalam PHP: 729. Kalendar Saya I

<?php class MyCalendar {
    /**
     * @var array
     */
    private $events;

    /**
     */
    function __construct() {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Books an event if it does not cause a double booking
     *
     * @param Integer $start
     * @param Integer $end
     * @return Boolean
     */
    function book($start, $end) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * $obj = MyCalendar();
 * $ret_1 = $obj->book($start, $end);
 */

// Example Usage:
$myCalendar = new MyCalendar();
var_dump($myCalendar->book(10, 20)); // true, no conflicts, booking added
var_dump($myCalendar->book(15, 25)); // false, conflict with [10, 20]
var_dump($myCalendar->book(20, 30)); // true, no conflicts, booking added
?>

Penjelasan:

1. Pembina (__construct): Memulakan tatasusunan kosong $events untuk menjejaki semua acara yang ditempah.

2. Fungsi Tempahan (buku):

   • Ia memerlukan permulaan dan penghujung acara baharu.
   • Ia berulang melalui senarai acara yang ditempah sebelum ini dan menyemak sebarang pertindihan:
     • Pertindihan berlaku jika acara baharu bermula sebelum acara sedia ada berakhir ($start dan berakhir selepas acara sedia ada bermula ($end > $bookedStart).
   • Jika sebarang pertindihan ditemui, fungsi tersebut akan mengembalikan palsu, bermakna acara tidak boleh ditempah.
   • Jika tiada konflik ditemui, acara akan ditambahkan pada tatasusunan $events dan fungsi kembali benar untuk menunjukkan tempahan yang berjaya.

Kerumitan Masa:

• Tempahan Acara: Setiap panggilan untuk menempah melibatkan menyemak acara baharu terhadap semua acara yang ditempah sebelum ini. Ini membawa kepada kerumitan masa O(n) untuk setiap operasi tempahan, dengan n ialah bilangan acara yang ditempah sebelum ini.
• Kerumitan Angkasa: Kerumitan ruang ialah O(n) kerana kami menyimpan sehingga n peristiwa dalam tatasusunan.

Contoh Panduan:

1. Tempahan Pertama (buku(10, 20)):

   • Tiada acara sebelumnya, jadi acara [10, 20] berjaya ditempah.
   • Output: benar

2. Tempahan Kedua (buku(15, 25)):

   • Acara baharu [15, 25] bercanggah dengan acara yang ditempah sebelum ini [10, 20] kerana terdapat pertindihan dalam selang masa (15 adalah antara 10 dan 20).
   • Output: palsu

3. Tempahan Ketiga (buku(20, 30)):

   • Acara baharu [20, 30] tidak bertindih dengan [10, 20] kerana masa mula acara baharu adalah tepat apabila acara pertama tamat (tiada pertindihan kerana ia adalah selang separuh terbuka).
   • Output: benar

Pendekatan mudah ini mengendalikan sehingga 1000 acara dengan cekap sambil mengekalkan kejelasan dan ketepatan.

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 I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!