。私のカレンダーⅡ-PHPチュートリアル-php.cn

。私のカレンダーⅡ

DDD

リリース： 2024-09-28 06:15:01

オリジナル

302 人が閲覧しました

. My Calendar II

731。私のカレンダー II

難易度: 中

トピック: 配列、二分探索、設計、セグメントツリー、接頭辞の合計、順序付きセット

あなたはカレンダーとして使用するプログラムを実装しています。イベントを追加してもトリプルブッキングが発生しない場合は、新しいイベントを追加できます。

トリプルブッキングは、3 つのイベントに空ではない交差がある場合に発生します (つまり、ある瞬間が 3 つのイベントすべてに共通です)。

イベントは、半開間隔 [start, end) での予約を表す start と end の整数のペアとして表すことができます。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

ヒント:

解決策:

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";
?>

ログイン後にコピー

説明：