。我的日曆我

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通電話預訂。

提示：

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

解：

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

計劃：

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

讓我們用 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
?>

解釋：

1. 建構子 (__construct)：初始化一個空數組 $events 以追蹤所有預訂的事件。

2. 預訂功能（書）：

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

時間複雜度：

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

演練範例：

1. 第一次預訂（書（10, 20））:

   • 之前沒有活動，所以活動[10, 20]成功預訂。
   • 輸出：true

2. 第二次預訂（書（15, 25））:

   • 新的活動 [15, 25] 與先前預訂的活動 [10, 20] 發生衝突，因為時間間隔有重疊（15 位於 10 和 20 之間）。
   • 輸出：假

3. 第三次預訂（書（20, 30））:

   • 新事件 [20, 30] 不會與 [10, 20] 重疊，因為新事件的開始時間恰好是第一個事件結束的時間（因為是半開區間，所以沒有重疊）。
   • 輸出：true

這種簡單的方法可有效處理多達 1000 個事件，同時保持清晰度和正確性。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。我的日曆我的詳細內容。更多資訊請關注PHP中文網其他相關文章！