最多可以参加的会议数目 II

标签: 数组 二分查找 动态规划 排序

难度: Hard

给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。

 

示例 1：

输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。

示例 2：

输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。

示例 3：

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。

 

提示：

  • 1 <= k <= events.length
  • 1 <= k * events.length <= 106
  • 1 <= startDayi <= endDayi <= 109
  • 1 <= valuei <= 106

Submission

运行时间: 562 ms

内存: 90.0 MB

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda e:e[1]) # 按结束时间的先后进行排序

        n = len(events)
        dp=[[0]*(k+1) for i in range(n+1)]
        # dp[i][j]表示从前i个会议中选择j个会议的最大价值和


        for i in range(1,n+1):
            # 通过遍历找到某个会议开始前的最晚结束的会议！这里遍历不会超时，放心遍历
            start = events[i-1][0]
            end = events[i-1][1]
            val = events[i-1][2]

            last = -1
            for j in range(i-1,-1,-1):
                if events[j][1]<start:
                    last = j
                    break

            for j in range(1,k+1):
                # 前一项是不参加当前会议，后一项是参加当前会议
                dp[i][j] = max(dp[i-1][j], dp[last+1][j-1]+val)

        return dp[n][k]

Explain

该题解主要使用了动态规划的方法来解决问题。首先，将事件按照结束时间进行排序，以保证在处理事件的顺序时可以按照时间的顺序来处理。定义一个二维的dp数组，其中dp[i][j]代表考虑前i个事件，最多参加j个事件时能获得的最大价值。对于每一个事件，我们可以选择参加或不参加。如果不参加，则最大价值与前i-1个事件选择j个的价值相同，即dp[i][j] = dp[i-1][j]。如果选择参加，我们需要找到在该事件开始之前结束的最晚的事件，这可以通过从当前事件向前搜索，找到第一个结束时间小于当前事件开始时间的事件来实现。如果找到这样的事件，参加当前事件的价值是该事件的价值加上在找到的事件之前的最大价值，即dp[i][j] = max(dp[i][j], dp[last+1][j-1] + value)。最终，dp[n][k]中存储的就是在所有事件中选择最多k个事件能得到的最大价值。

时间复杂度: O(n^2 * k)

空间复杂度: O(n * k)

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda e:e[1]) # Sort events by their end times

        n = len(events)
        dp = [[0] * (k + 1) for i in range(n + 1)] # dp[i][j] represents the maximum value from choosing j events among the first i events

        for i in range(1, n + 1):
            start = events[i - 1][0]
            end = events[i - 1][1]
            val = events[i - 1][2]

            last = -1
            for j in range(i - 1, -1, -1): # Find the last event that ends before the current event starts
                if events[j][1] < start:
                    last = j
                    break

            for j in range(1, k + 1): # Update dp values for up to k events
                dp[i][j] = max(dp[i - 1][j], dp[last + 1][j - 1] + val) # Max value without current event or with current event

        return dp[n][k] # The maximum value with at most k events

Explore

简单地遍历前面所有事件来寻找`在该事件开始之前结束的最晚的事件`并不是效率最优的方法，因为这样做的时间复杂度为O(n^2)，其中n是事件的数量。更高效的方法是使用二分搜索（Binary Search），因为事件已经根据结束时间排序。通过二分搜索，我们可以将寻找该事件的时间复杂度降低到O(log n)，从而使整体算法的时间复杂度优化到O(n log n)。在实现时，可以维护一个根据结束时间排序的事件列表，然后对于每个事件使用二分搜索来查找最晚且在当前事件开始前结束的事件。

`dp[last + 1][j - 1] + val`在状态转移方程中表示如果选择参加当前事件，我们应该加上当前事件的价值(val)和在此事件开始之前可以参与的最多事件的最大价值。这里的`last`是在当前事件开始之前结束的最晚的事件的索引，`last + 1`代表在`last`事件之后的第一个事件，也就是说`dp[last + 1][j - 1]`是考虑从`last + 1`到当前事件之前的事件中选择最多`j-1`个事件时的最大价值。这种方法确保了事件选择的不重叠，因为`last`事件结束的时间是在当前事件开始之前，所以这两个事件不会冲突。

在初始化dp数组为0是基于假设所有事件的价值非负的情况下的标准做法，这样做的目的是确保在不选择任何事件时的价值为0。如果事件的价值可能为负数，那么简单地初始化为0可能不再适用，因为这可能导致选择负价值事件而降低总价值。在这种情况下，可能需要调整初始化策略或在状态转移时考虑是否选择负价值事件。例如，可以初始化为一个足够大的负数以确保不会错误地选择负价值事件，或者在更新dp值时添加条件检查事件的价值。