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：

输入：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 <= 10^5
  • events[i].length == 3
  • 1 <= startTimei <= endTimei <= 10^9
  • 1 <= valuei <= 10^6

解题思路

这道题要求选择最多两个不重叠的事件，使价值和最大。关键在于高效地找到对于每个事件，在它之后能选择的最大价值事件。

解法一：排序 + 后缀最大值 首先按事件的开始时间排序。对于每个事件，我们需要找到在它结束后开始的所有事件中价值最大的那个。可以预处理一个后缀最大值数组，记录从每个位置开始往后的最大价值。

解法二：排序 + 二分查找（推荐） 同样按开始时间排序，然后从右到左维护一个后缀最大值数组。对于每个事件，使用二分查找找到第一个开始时间大于当前事件结束时间的事件位置，然后在后缀最大值数组中查询最大价值。

解法三：扫描线算法 将事件按时间点展开为开始和结束事件，使用扫描线算法处理。

核心思路是：

  1. 按开始时间排序所有事件
  2. 预处理后缀最大值数组
  3. 对每个事件，找到它之后不重叠的最大价值事件
  4. 计算单个事件价值和两个事件价值的最大值

代码实现

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        int n = events.size();
        
        // 计算后缀最大值
        vector<int> suffixMax(n);
        suffixMax[n-1] = events[n-1][2];
        for (int i = n-2; i >= 0; i--) {
            suffixMax[i] = max(suffixMax[i+1], events[i][2]);
        }
        
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            result = max(result, events[i][2]); // 只选当前事件
            
            // 二分查找第一个不重叠的事件
            int left = i + 1, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (events[mid][0] > events[i][1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            
            // 如果找到了不重叠的事件
            if (left < n) {
                result = max(result, events[i][2] + suffixMax[left]);
            }
        }
        
        return result;
    }
};

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort()
        n = len(events)
        
        # 计算后缀最大值
        suffix_max = [0] * n
        suffix_max[n-1] = events[n-1][2]
        for i in range(n-2, -1, -1):
            suffix_max[i] = max(suffix_max[i+1], events[i][2])
        
        result = 0
        
        for i in range(n):
            result = max(result, events[i][2])  # 只选当前事件
            
            # 二分查找第一个不重叠的事件
            left, right = i + 1, n
            while left < right:
                mid = (left + right) // 2
                if events[mid][0] > events[i][1]:
                    right = mid
                else:
                    left = mid + 1
            
            # 如果找到了不重叠的事件
            if left < n:
                result = max(result, events[i][2] + suffix_max[left])
        
        return result

public class Solution {
    public int MaxTwoEvents(int[][] events) {
        Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));
        int n = events.Length;
        
        // 计算后缀最大值
        int[] suffixMax = new int[n];
        suffixMax[n-1] = events[n-1][2];
        for (int i = n-2; i >= 0; i--) {
            suffixMax[i] = Math.Max(suffixMax[i+1], events[i][2]);
        }
        
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            result = Math.Max(result, events[i][2]); // 只选当前事件
            
            // 二分查找第一个不重叠的事件
            int left = i + 1, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (events[mid][0] > events[i][1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            
            // 如果找到了不重叠的事件
            if (left < n) {
                result = Math.Max(result, events[i][2] + suffixMax[left]);
            }
        }
        
        return result;
    }
}

var maxTwoEvents = function(events) {
    events.sort((a, b) => a[0] - b[0]);
    const n = events.length;
    
    // 计算后缀最大值
    const suffixMax = new Array(n);
    suffixMax[n-1] = events[n-1][2];
    for (let i = n-2; i >= 0; i--) {
        suffixMax[i] = Math.max(suffixMax[i+1], events[i][2]);
    }
    
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        result = Math.max(result, events[i][2]); // 只选当前事件
        
        // 二分查找第一个不重叠的事件
        let left = i + 1, right = n;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (events[mid][0] > events[i][1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        // 如果找到了不重叠的事件
        if (left < n) {
            result = Math.max(result, events[i][2] + suffixMax[left]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 排序的时间复杂度为 O(n log n)
  • 预处理后缀最大值数组需要 O(n) 时间
  • 对每个事件进行二分查找，总共 O(n log n) 时间
  • 后缀最大值数组需要 O(n) 额外空间

相关题目