。我的日历二-php教程-PHP中文网

。我的日历二

DDD

发布： 2024-09-28 06:15:01

原创

255 人浏览过

. My Calendar II

731。我的日历 II

难度：中等

主题：数组、二分查找、设计、线段树、前缀和、有序集

您正在实现一个程序来用作您的日历。如果添加活动不会导致三重预订。

，我们可以添加新活动

三重预订发生在三个事件有一些非空交叉点时（即，某些时刻是所有三个事件共有的。）。

事件可以表示为一对整数 start 和 end，表示半开区间 [start, end) 上的预订，实数 x 的范围使得 start

实现 MyCalendarTwo 类：

MyCalendarTwo() 初始化日历对象。
boolean book(int start, int end) 如果事件可以成功添加到日历而不会导致三重预订，则返回true。否则，返回 false 并且不将事件添加到日历。

示例1：

输入：

  ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
  [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

登录后复制

输出：

  [null, true, true, true, false, true, true]

登录后复制

说明：

  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.

登录后复制

约束：

0 9
最多可拨打1000个电话进行预订。

提示：

存储两个排序的间隔列表：一个列表将是至少单次预订的所有时间，另一个列表将是所有肯定被双重预订的时间。如果两次预订均不冲突，则预订成功，您应相应更新您的单次和双人预订。

解决方案：

我们需要维护两个预订列表：

单次预订：跟踪一次预订的所有活动的列表。
双重预订：跟踪所有双重预订活动的列表。

当请求新活动时，我们需要检查是否会导致三重预订。为此：

我们首先检查新活动是否与双重预订列表中的任何时间间隔重叠。如果是这样，我们无法添加该活动，因为这会导致三重预订。
如果与双重预订没有重叠，我们会检查单次预订列表，并将新活动与现有活动的重叠添加到双重预订中 列表。

最后，如果活动通过了两项检查，我们会将其添加到单次预订列表中。

让我们用 PHP 实现这个解决方案：731。我的日历 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";
?>

登录后复制

解释：

构造函数(__construct)：用两个空数组初始化日历对象，以存储单次预订和双次预订。
图书功能（书籍）：
- 该函数获取事件的开始和结束。
- 它首先检查事件是否与 doubleBookings 列表中的任何间隔重叠。如果是，该函数将返回 false，因为这将导致三重预订。
- 如果没有三重预订，它会检查单次预订列表中活动的重叠情况。发现的任何重叠都会添加到双重预订列表中，因为它现在代表双重预订。
- 最后，该事件被添加到 singleBookings 列表中，并且函数返回 true。