搜尋
首頁後端開發php教程。我的日曆二

。我的日曆二

Sep 28, 2024 am 06:15 AM

. My Calendar II

731. My Calendar II

Difficulty: Medium

Topics: Array, Binary Search, Design, Segment Tree, Prefix Sum, Ordered Set

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start

Implement the MyCalendarTwo class:

  • MyCalendarTwo() Initializes the calendar object.
  • boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Example 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]
  • Explanation:
  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.

Constraints:

  • 0 9
  • At most 1000 calls will be made to book.

Hint:

  1. Store two sorted lists of intervals: one list will be all times that are at least single booked, and another list will be all times that are definitely double booked. If none of the double bookings conflict, then the booking will succeed, and you should update your single and double bookings accordingly.

Solution:

We need to maintain two lists of bookings:

  1. Single Bookings: A list that keeps track of all events that are booked once.
  2. Double Bookings: A list that keeps track of all events that are double booked.

When a new event is requested, we need to check if it will cause a triple booking. To do that:

  • We first check if the new event overlaps with any of the intervals in the double bookings list. If it does, we cannot add the event because it would lead to a triple booking.
  • If there is no overlap with the double bookings, we then check the single bookings list and add the overlap of the new event with existing events to the double bookings list.

Finally, if the event passes both checks, we add it to the single bookings list.

Let's implement this solution in PHP: 731. My Calendar II

<?php class MyCalendarTwo {
    /**
     * @var array
     */
    private $singleBookings;
    /**
     * @var array
     */
    private $doubleBookings;

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

    /**
     * @param Integer $start
     * @param Integer $end
     * @return Boolean
     */
    function book($start, $end) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * $obj = MyCalendarTwo();
 * $ret_1 = $obj->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";
?>

Explanation:

  1. Constructor (__construct): Initializes the calendar object with two empty arrays to store the single bookings and double bookings.

  2. Book Function (book):

    • The function takes the start and end of an event.
    • It first checks if the event overlaps with any interval in the doubleBookings list. If it does, the function returns false because it would result in a triple booking.
    • If there's no triple booking, it checks the overlap with events in the singleBookings list. Any overlap found is added to the doubleBookings list, as it now represents a double booking.
    • Finally, the event is added to the singleBookings list and the function returns true.

Time Complexity:

  • The time complexity is approximately O(n) for each booking operation, where n is the number of bookings made so far. This is because for each booking, we may need to check all previous bookings in both the singleBookings and doubleBookings lists.

This solution efficiently handles up to 1000 calls to the book function as required by the problem constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

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

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
您如何防止與會議有關的跨站點腳本(XSS)攻擊?您如何防止與會議有關的跨站點腳本(XSS)攻擊?Apr 23, 2025 am 12:16 AM

要保護應用免受與會話相關的XSS攻擊,需採取以下措施:1.設置HttpOnly和Secure標誌保護會話cookie。 2.對所有用戶輸入進行輸出編碼。 3.實施內容安全策略(CSP)限制腳本來源。通過這些策略,可以有效防護會話相關的XSS攻擊,確保用戶數據安全。

您如何優化PHP會話性能?您如何優化PHP會話性能?Apr 23, 2025 am 12:13 AM

优化PHP会话性能的方法包括:1.延迟会话启动,2.使用数据库存储会话,3.压缩会话数据,4.管理会话生命周期,5.实现会话共享。这些策略能显著提升应用在高并发环境下的效率。

什麼是session.gc_maxlifetime配置設置?什麼是session.gc_maxlifetime配置設置?Apr 23, 2025 am 12:10 AM

theSession.gc_maxlifetimesettinginphpdeterminesthelifespanofsessiondata,setInSeconds.1)它'sconfiguredinphp.iniorviaini_set().2)abalanceisesneededeededeedeedeededto toavoidperformance andunununununexpectedLogOgouts.3)

您如何在PHP中配置會話名?您如何在PHP中配置會話名?Apr 23, 2025 am 12:08 AM

在PHP中,可以使用session_name()函數配置會話名稱。具體步驟如下:1.使用session_name()函數設置會話名稱,例如session_name("my_session")。 2.在設置會話名稱後,調用session_start()啟動會話。配置會話名稱可以避免多應用間的會話數據衝突,並增強安全性,但需注意會話名稱的唯一性、安全性、長度和設置時機。

您應該多久再生一次會話ID?您應該多久再生一次會話ID?Apr 23, 2025 am 12:03 AM

會話ID應在登錄時、敏感操作前和每30分鐘定期重新生成。 1.登錄時重新生成會話ID可防會話固定攻擊。 2.敏感操作前重新生成提高安全性。 3.定期重新生成降低長期利用風險,但需權衡用戶體驗。

如何在PHP中設置會話cookie參數?如何在PHP中設置會話cookie參數?Apr 22, 2025 pm 05:33 PM

在PHP中設置會話cookie參數可以通過session_set_cookie_params()函數實現。 1)使用該函數設置參數,如過期時間、路徑、域名、安全標誌等;2)調用session_start()使參數生效;3)根據需求動態調整參數,如用戶登錄狀態;4)注意設置secure和httponly標誌以提升安全性。

在PHP中使用會議的主要目的是什麼?在PHP中使用會議的主要目的是什麼?Apr 22, 2025 pm 05:25 PM

在PHP中使用會話的主要目的是維護用戶在不同頁面之間的狀態。 1)會話通過session_start()函數啟動,創建唯一會話ID並存儲在用戶cookie中。 2)會話數據保存在服務器上,允許在不同請求間傳遞數據,如登錄狀態和購物車內容。

您如何在子域中分享會議?您如何在子域中分享會議?Apr 22, 2025 pm 05:21 PM

如何在子域名間共享會話?通過設置通用域名的會話cookie實現。 1.在服務器端設置會話cookie的域為.example.com。 2.選擇合適的會話存儲方式,如內存、數據庫或分佈式緩存。 3.通過cookie傳遞會話ID,服務器根據ID檢索和更新會話數據。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!