两个最好的不重叠事件

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