兩個最好的不重疊事件

2054。兩個最好的不重疊的事件

難度：中

主題：陣列、二分查找、動態規劃、排序、堆疊（優先權佇列）

您將獲得一個0 索引 2D 事件整數數組，其中events[i] = [startTime_i, endTime_i, value_我]。第i^第活動從startTime_i開始，到endTime_i結束，如果您參加本次活動，您將獲得價值value_i 。您可以選擇最多兩個不重疊的活動參加，以使它們的值之和最大化。

返回此最大總和。

請注意，開始時間和結束時間包含：也就是說，您不能參加兩個活動，其中一個活動同時開始，另一個活動同時結束。更具體地說，如果您參加結束時間為 t 的活動，則下一個活動必須在 t 1 或之後開始。

範例1：

• 輸入： events = [[1,3,2],[4,5,2],[2,4,3]]
• 輸出： 4
• 解釋： 選擇綠色事件 0 和 1，總和為 2 2 = 4。

範例2：

• 輸入： events = [[1,3,2],[4,5,2],[1,5,5]]
• 輸出： 5
• 解釋：選擇事件 2，總和為 5。

範例 3：

• 輸入： events = [[1,5,3],[1,5,1],[6,6,5]]
• 輸出： 8
• 解釋： 選擇事件 0 和 2，總和為 3 5 = 8。

約束：

• 2 5
• 事件[i].length == 3
• 1 i i 9
• 1 i 6

提示：

1. 根據事件的開始時間對事件進行排序有何幫助？結束時間怎麼樣？
2. 如何快速得到與我們所選的區間不相交的區間的最高分？

解：

我們可以使用以下方法：

方法

1. 以結束時間對活動進行排序:

   • 排序幫助我們使用二分搜尋有效地找到不重疊的事件。

2. 非重疊事件的二分搜尋:

   • 使用二分搜尋尋找在目前事件開始時間之前結束的最新事件。這確保了不重疊。

3. 使用最大追蹤的動態規劃:

   • 在迭代排序的事件時，維護事件的最大值直到當前事件。這使我們能夠快速計算兩個事件的最大總和。

4. 迭代併計算最大值和:

   • 對於每個事件，使用以下方法計算可能的總和：
     • 僅限當前活動。
     • 當前事件與使用二分搜尋找到的最佳非重疊事件相結合。

讓我們用 PHP 實作這個解決方案：2054。兩個最佳不重疊事件

<?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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是兩個最好的不重疊事件的詳細內容。更多資訊請關注PHP中文網其他相關文章！