。我的日历我

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中文网其他相关文章！