两个最好的不重叠活动

标签: 数组 二分查找 动态规划 排序 堆（优先队列）

难度: Medium

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值 valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。

请你返回价值之和的 最大值 。

注意，活动的开始时间和结束时间是 包括 在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]
输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

Example 1 Diagram

输入：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 <= events.length <= 105
  • events[i].length == 3
  • 1 <= startTimei <= endTimei <= 109
  • 1 <= valuei <= 106

Submission

运行时间: 188 ms

内存: 53.0 MB

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int: 
        events.sort(key=itemgetter(0))
        end_order = sorted(events, key=itemgetter(1))

        n = len(events)
        left = 0
        ans = 0
        pre_max = 0

        for start, end, value in events:
            while left < n and start > end_order[left][1]:
                pre_max = max(pre_max, end_order[left][2])
                left += 1
            ans = max(ans, value + pre_max)
        
        return ans

Explain

该题解采用排序和扫描的方法来寻找最大的价值和。首先，原始活动列表按照活动的开始时间进行排序，同时创建一个以结束时间排序的活动列表。通过这两个排序列表，算法试图找到不重叠的最佳两个活动组合。使用一个指针 'left' 来遍历按结束时间排序的列表，而主循环遍历按开始时间排序的列表。在主循环中，对于每个活动，我们使用 'left' 指针移动到所有结束时间早于当前活动开始时间的活动，并更新这些活动中的最大价值 'pre_max'。然后，将当前活动的价值加上这个 'pre_max'，并更新整体的最大价值 'ans'。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int: 
        # 按开始时间对活动进行排序
        events.sort(key=itemgetter(0))
        # 创建一个按结束时间排序的活动列表
        end_order = sorted(events, key=itemgetter(1))

        n = len(events)
        left = 0
        ans = 0
        pre_max = 0

        # 遍历每个活动，检查是否可以与之前的不重叠活动组合以达到最大价值
        for start, end, value in events:
            # 更新left指针，确保不与当前考虑的活动重叠
            while left < n and start > end_order[left][1]:
                pre_max = max(pre_max, end_order[left][2])
                left += 1
            # 计算当前活动与之前最大价值活动的组合价值
            ans = max(ans, value + pre_max)
        
        return ans

Explore

在题解中，‘left’指针用于遍历按结束时间排序的活动列表‘end_order’。算法的主逻辑是确保在处理当前活动（按开始时间排序）时，‘left’指针指向的活动不与当前活动重叠。这是通过检查‘left’指向的活动的结束时间是否小于当前活动的开始时间来实现的。如果‘end_order[left][1]’（即‘left’指向的活动的结束时间）小于‘events[i][0]’（当前活动的开始时间），则‘left’指针向右移动。这个过程持续进行，直到‘end_order[left][1]’不再小于‘events[i][0]’。这样，‘left’指针就始终指向那些结束时间早于当前考虑活动的开始时间的活动，从而确保选取的活动不会重叠。

在更新‘pre_max’的过程中，算法通过移动‘left’指针来更新在当前考虑的活动开始之前结束的所有活动的最大价值。‘pre_max’始终保留了‘left’指针之前所有活动的最大价值。由于‘left’指针从头开始遍历，并且只在满足条件时向右移动，且每个活动的价值只有在其结束时间小于当前活动的开始时间时才会被考虑，因此算法不会遗漏任何可能的活动。每次循环时‘pre_max’都是基于之前结算过的最大价值，确保了每一步的正确性和完整性。

是的，算法确实考虑了只参加一个活动的情况。这是通过在计算可能的两个活动组合的最大价值时同时确保更新单个活动的最大价值。在每次循环中，‘ans’变量被更新为当前活动价值‘value’与之前最大的活动价值‘pre_max’的和的最大值，同时也直接与当前活动的价值‘value’比较。这样，即使没有找到一个有效的、不重叠的第二个活动，算法也会考虑当前活动本身的价值，从而确保了即使是单个活动也可能被认为是最大价值的情况。