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:
- 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:
- Single Bookings: A list that keeps track of all events that are booked once.
- 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:
Constructor (__construct): Initializes the calendar object with two empty arrays to store the single bookings and double bookings.
-
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:
- GitHub
The above is the detailed content of . My Calendar II. For more information, please follow other related articles on the PHP Chinese website!

Long URLs, often cluttered with keywords and tracking parameters, can deter visitors. A URL shortening script offers a solution, creating concise links ideal for social media and other platforms. These scripts are valuable for individual websites a

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

This is the second and final part of the series on building a React application with a Laravel back-end. In the first part of the series, we created a RESTful API using Laravel for a basic product-listing application. In this tutorial, we will be dev

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

The 2025 PHP Landscape Survey investigates current PHP development trends. It explores framework usage, deployment methods, and challenges, aiming to provide insights for developers and businesses. The survey anticipates growth in modern PHP versio

In this article, we're going to explore the notification system in the Laravel web framework. The notification system in Laravel allows you to send notifications to users over different channels. Today, we'll discuss how you can send notifications ov


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

SAP NetWeaver Server Adapter for Eclipse
Integrate Eclipse with SAP NetWeaver application server.

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),
