重複しないイベントのベスト 2 つ

2054年。重複しないベスト 2 つのイベント

難易度: 中

トピック: 配列、二分探索、動的プログラミング、ソート、ヒープ (優先キュー)

イベントの 0 インデックス付き 2D 整数配列が与えられます。ここで、 events[i] = [startTime_i、endTime_i、value_私]。 i^番目イベントはstartTime_iに始まりendTime_iに終了します。このイベントに参加すると、value_{iの値を受け取ります。} 。 重複しない最大 2 つのイベントを選択して、それらの値の合計が最大化されるようにすることができます。

この最大の合計を返します。

開始時間と終了時間は包括的であることに注意してください。つまり、一方が開始し、他方が同時に終了する 2 つのイベントに参加することはできません。具体的には、終了時刻が t のイベントに参加した場合、次のイベントは t 1 以降に開始する必要があります。

例 1:

• 入力: イベント = [[1,3,2],[4,5,2],[2,4,3]]
• 出力: 4
• 説明: 緑色のイベント、合計 2 2 = 4 となる 0 と 1 を選択します。

例 2:

• 入力: イベント = [[1,3,2],[4,5,2],[1,5,5]]
• 出力: 5
• 説明: 合計が 5 になるイベント 2 を選択します。

例 3:

• 入力: イベント = [[1,5,3],[1,5,1],[6,6,5]]
• 出力: 8
• 説明: 合計が 3 5 = 8 となるイベント 0 と 2 を選択します。

制約:

• 2 105
イベント[i].length == 3
• _{1 i i ⁹}
• _{1 i ⁶}

ヒント:

開始時間に基づいてイベントを並べ替えることはどのように役立ちますか?終了時間はどうですか?
選択した区間と交差しない区間の最大スコアを素早く取得するにはどうすればよいでしょうか?

解決策:

次のアプローチを使用できます:

アプローチ

1. イベントを終了時間で並べ替えます

   :
   並べ替えは、二分探索を使用して重複しないイベントを効率的に見つけるのに役立ちます。

2. 重複しないイベントの二分探索

   :
   • 二分検索を使用して、現在のイベントの開始時間より前に終了する最新のイベントを検索します。これにより、重複がなくなります。

3. 最大トラッキングを使用した動的プログラミング:

   • 並べ替えられたイベントを反復処理する際、イベントの最大値を現在の値まで維持します。これにより、2 つのイベントの最大合計をすばやく計算できます。

4. 最大合計を反復して計算します:

   • 各イベントについて、以下を使用して可能な合計を計算します。
     • 現在のイベントのみ。
     • 現在のイベントと、二分探索を使用して見つかった重複しない最良のイベントを組み合わせたものです。

このソリューションを PHP で実装してみましょう: 2054。重複しないベスト 2 つのイベント

<?php /**
 * @param Integer[][] $events
 * @return Integer
 */
function maxTwoEvents($events) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage:
$events1 = [[1, 3, 2], [4, 5, 2], [2, 4, 3]];
$events2 = [[1, 3, 2], [4, 5, 2], [1, 5, 5]];
$events3 = [[1, 5, 3], [1, 5, 1], [6, 6, 5]];

echo maxTwoEvents($events1) . "\n"; // Output: 4
echo maxTwoEvents($events2) . "\n"; // Output: 5
echo maxTwoEvents($events3) . "\n"; // Output: 8
?>

説明：

1. 並べ替え:

   • イベントは終了時刻によって並べ替えられるため、重複しない最後のイベントを効率的に検索できます。

2. 二分探索:

   • 各イベントについて、二分探索により、現在のイベントが開始する前に終了する最新のイベントが特定されます。

3. 最大追跡:

   • 現在のインデックスまでのイベントの最大値を格納する配列 maxUpTo を維持します。これにより、以前のインデックスの最大値の再計算が回避されます。

4. 最大合計の計算:

   • 各イベントについて、その値と重複しない最良のイベントの値の合計を計算します。それに応じてグローバル最大合計を更新します。

複雑さの分析

• 並べ替え: O(n log n)
• 各イベントの二分探索: O(log n)、n 回繰り返し → O(n log n)
• 全体: O(n log n)

このソリューションは効率的であり、制約内でうまく機能します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が重複しないイベントのベスト 2 つの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。