。私のカレンダーⅡ

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
予約のために最大 1,000 件の電話がかけられます。

ヒント:

間隔の 2 つのソートされたリストを保存します。1 つのリストは少なくとも単一予約されているすべての時間となり、もう 1 つのリストは明らかに二重予約されているすべての時間になります。どのダブル予約も競合しない場合、予約は成功するため、それに応じてシングル予約とダブル予約を更新する必要があります。

解決策:

2 つの予約リストを維持する必要があります:

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 つの空の配列を使用してカレンダー オブジェクトを初期化します。

2. ブック関数 (ブック)

   :
   この関数はイベントの開始と終了を受け取ります。
   まず、イベントが doubleBookings リスト内のいずれかの間隔と重複するかどうかを確認します。該当する場合、トリプル予約が発生するため、この関数は false を返します。
   トリプル予約がない場合は、singleBookings リスト内のイベントとの重複をチェックします。重複が見つかった場合は、ダブルブッキングを表すため、doubleBookings リストに追加されます。
   最後に、イベントが singleBookings リストに追加され、関数は true を返します。

時間計算量:

• 各予約操作の時間計算量は約 O(n)
です。ここで、n はこれまでに行われた予約の数です。これは、予約ごとに、singleBookings リストと doubleBookings リストの両方で以前の予約をすべて確認する必要がある場合があるためです。

このソリューションは、問題の制約に応じて book 関数への最大 1000 回の呼び出しを効率的に処理します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ

にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。私のカレンダーⅡの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。