。我的日曆我-php教程-PHP中文網

。我的日曆我

Mary-Kate Olsen

發布： 2024-09-27 06:14:03

原創

455 人瀏覽過

. My Calendar I

729。我的日曆我

難度：中

主題：陣列、二分搜尋、設計、線段樹、有序集

您正在實作一個程式來用作您的日曆。如果新增活動不會導致重複預訂。

，我們可以新增活動

雙重預訂發生在兩個事件有一些非空交叉點時（即，某些時刻是兩個事件共有的。）。

事件可以表示為一對整數 start 和 end，表示半開區間 [start, end) 上的預訂，實數 x 的範圍使得 start

實作 MyCalendar 類別：

MyCalendar() 初始化日曆物件。
boolean book(int start, int end) 如果事件可以成功加入到行事曆而不會導致重複預約，則傳回true。否則，返回 false 並且不將事件新增至日曆。

範例1：

輸入：

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

登入後複製

輸出：

  [null, true, false, true]

登入後複製

說明：

  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.

登入後複製

約束：

0 9
最多可撥打1000通電話預訂。

提示：

將事件儲存為間隔的排序清單。如果所有事件都不衝突，則可以新增事件。

解：

我們需要儲存每個活動，並在預訂之前檢查新活動是否與任何現有活動衝突。由於最多允許 1000 次預訂電話，因此我們可以將活動儲存在清單中，並在預訂新活動時迭代它們以檢查是否有重疊。

計劃：

儲存事件：我們將維護一個列表，其中每個條目都是一對代表預訂時間間隔的[開始，結束]。
檢查衝突：在新增活動之前，我們將遍歷預訂的活動列表，並檢查新活動是否與任何現有活動衝突。如果新事件的開始時間小於現有事件的結束時間，且新事件的結束時間大於現有事件的開始時間，則會發生重疊。
預訂活動：如果沒有發現衝突，我們會將新活動加入我們的預訂清單。

讓我們用 PHP 實作這個解：729。我的行事曆我

<?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
?>

登入後複製

解釋：

建構子 (__construct)：初始化一個空數組 $events 以追蹤所有預訂的事件。
預訂功能（書）：
- 它需要一個新事件的開始和結束。
- 它會遍歷先前預訂的活動清單並檢查是否有重疊：
  - 如果新活動在現有活動結束之前開始（$start 並且在現有活動開始之後結束（$end > $bookedStart），則會發生重疊。
- 如果發現任何重疊，則函數將傳回 false，這表示該活動無法預訂。
- 如果沒有發現衝突，則將該事件加入$events陣列中，函數傳回true表示預訂成功。

時間複雜度：

預訂活動：每次致電預訂都需要對照所有先前預訂的活動來檢查新活動。這導致每個預訂操作的時間複雜度為 O(n)，其中 n 是先前預訂的事件的數量。
空間複雜度：空間複雜度為 O(n)，因為我們在陣列中儲存最多 n 個事件。

演練範例：

第一次預訂（書（10, 20））:
- 之前沒有活動，所以活動[10, 20]成功預訂。
- 輸出：true
第二次預訂（書（15, 25））:
- 新的活動 [15, 25] 與先前預訂的活動 [10, 20] 發生衝突，因為時間間隔有重疊（15 位於 10 和 20 之間）。
- 輸出：假
第三次預訂（書（20, 30））:
- 新事件 [20, 30] 不會與 [10, 20] 重疊，因為新事件的開始時間恰好是第一個事件結束的時間（因為是半開區間，所以沒有重疊）。
- 輸出：true