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 。
注意你无法同时参加任何其他活动，因为它们时间上都有冲突。而且你也没有必要参加 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 <= 10^6
  • 1 <= startDayi <= endDayi <= 10^9
  • 1 <= valuei <= 10^6

解题思路

这是一道典型的动态规划问题，需要在有限制条件下选择最优子集。

核心思路：

  1. 预处理排序：首先按活动开始时间对所有活动进行排序，这样便于后续处理时间冲突。

  2. 状态定义：使用动态规划，定义 dp[i][j] 表示在前 i 个活动中选择不超过 j 个活动能获得的最大价值。

  3. 状态转移：对于每个活动 i，有两种选择：

    • 不选择当前活动：dp[i][j] = dp[i-1][j]
    • 选择当前活动：需要找到与当前活动不冲突的最近的前一个活动位置 prev，然后 dp[i][j] = dp[prev][j-1] + value[i]

  4. 二分查找优化：使用二分查找快速找到与当前活动不冲突的最大索引位置，即找到结束时间小于当前活动开始时间的最后一个活动。

  5. 空间优化：可以使用滚动数组或记忆化搜索进一步优化空间复杂度。

这种方法的关键在于正确处理活动间的时间冲突关系，并通过二分查找提高寻找无冲突活动的效率。最终答案为 dp[n][k]，其中 n 是活动总数。

代码实现

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        sort(events.begin(), events.end());
        int n = events.size();
        
        // dp[i][j] = max value using at most j events from first i events
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            int start = events[i-1][0];
            int end = events[i-1][1];
            int value = events[i-1][2];
            
            // Find the latest event that doesn't conflict with current event
            int prev = 0;
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (events[mid][1] < start) {
                    prev = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            for (int j = 1; j <= k; j++) {
                // Don't take current event
                dp[i][j] = dp[i-1][j];
                // Take current event
                dp[i][j] = max(dp[i][j], dp[prev][j-1] + value);
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()
        n = len(events)
        
        # dp[i][j] = max value using at most j events from first i events
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            start, end, value = events[i-1]
            
            # Find the latest event that doesn't conflict with current event
            prev = 0
            left, right = 0, i - 1
            while left <= right:
                mid = (left + right) // 2
                if events[mid][1] < start:
                    prev = mid + 1
                    left = mid + 1
                else:
                    right = mid - 1
            
            for j in range(1, k + 1):
                # Don't take current event
                dp[i][j] = dp[i-1][j]
                # Take current event
                dp[i][j] = max(dp[i][j], dp[prev][j-1] + value)
        
        return dp[n][k]

public class Solution {
    public int MaxValue(int[][] events, int k) {
        Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));
        int n = events.Length;
        
        // dp[i,j] = max value using at most j events from first i events
        int[,] dp = new int[n + 1, k + 1];
        
        for (int i = 1; i <= n; i++) {
            int start = events[i-1][0];
            int end = events[i-1][1];
            int value = events[i-1][2];
            
            // Find the latest event that doesn't conflict with current event
            int prev = 0;
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (events[mid][1] < start) {
                    prev = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            for (int j = 1; j <= k; j++) {
                // Don't take current event
                dp[i,j] = dp[i-1,j];
                // Take current event
                dp[i,j] = Math.Max(dp[i,j], dp[prev,j-1] + value);
            }
        }
        
        return dp[n,k];
    }
}

var maxValue = function(events, k) {
    events.sort((a, b) => a[0] - b[0]);
    const n = events.length;
    
    // dp[i][j] = max value using at most j events from first i events
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        const [start, end, value] = events[i-1];
        
        // Find the latest event that doesn't conflict with current event
        let prev = 0;
        let left = 0, right = i - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (events[mid][1] < start) {
                prev = mid + 1;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        for (let j = 1; j <= k; j++) {
            // Don't take current event
            dp[i][j] = dp[i-1][j];
            // Take current event
            dp[i][j] = Math.max(dp[i][j], dp[prev][j-1] + value);
        }
    }
    
    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²k) 其中 n 是活动数量，对于每个活动都需要二分查找(O(log n))和状态转移(O(k))，但实际上二分查找的部分可以优化，最坏情况下仍是 O(n²k)
空间复杂度O(nk) 用于存储动态规划状态数组

相关题目