。我的日历二

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个电话进行预订。

提示：

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

解决方案：

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

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

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

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

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

让我们用 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";
?>

解释：

1. 构造函数(__construct)：用两个空数组初始化日历对象，以存储单次预订和双次预订。

2. 图书功能（书籍）：

   • 该函数获取事件的开始和结束。
   • 它首先检查事件是否与 doubleBookings 列表中的任何间隔重叠。如果是，该函数将返回 false，因为这将导致三重预订。
   • 如果没有三重预订，它会检查单次预订列表中活动的重叠情况。发现的任何重叠都会添加到双重预订列表中，因为它现在代表双重预订。
   • 最后，该事件被添加到 singleBookings 列表中，并且函数返回 true。

时间复杂度：

• 每次预订操作的时间复杂度约为 O(n)，其中 n 是迄今为止进行的预订数量。这是因为对于每个预订，我们可能需要在 singleBookings 和 doubleBookings 列表中检查所有之前的预订。

此解决方案可根据问题约束的要求有效处理多达 1000 次对 book 函数的调用。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。我的日历二的详细内容。更多信息请关注PHP中文网其他相关文章！