Medium

题目描述

给你一个数组 events，其中 events[i] = [startDayi, endDayi]。每个活动 i 都在 startDayi 开始，在 endDayi 结束。

你可以在任何满足 startDayi <= d <= endDayi 的日期 d 参加活动 i。在任何时间 d 你只能参加一个活动。

返回你可以参加的最大活动数量。

示例 1：

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有三个活动。
参加它们的一种方式如下所示。
第1天参加第一个活动。
第2天参加第二个活动。
第3天参加第三个活动。

示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4

约束：

  • 1 <= events.length <= 10^5
  • events[i].length == 2
  • 1 <= startDayi <= endDayi <= 10^5

解题思路

这是一个经典的贪心算法问题。核心思想是按天遍历，每天选择最紧迫的活动参加。

基本思路：

  1. 贪心策略：对于每一天，从所有可以参加的活动中，选择结束时间最早的活动。这样可以为后续的活动留出更多空间。

  2. 算法流程：

    • 将所有活动按开始时间排序
    • 使用最小堆维护当前可以参加的活动（按结束时间排序）
    • 遍历每一天：
      • 将这一天开始的所有活动加入堆
      • 移除已经结束的活动
      • 如果堆不为空，选择结束时间最早的活动参加

时间优化： 实际实现时可以按活动的开始时间遍历，而不是按天遍历，这样可以避免遍历没有活动的日期。

为什么选择结束时间最早的活动？ 因为结束时间越早的活动越紧迫，如果不在当前时间参加，未来可能就没有机会了。而结束时间较晚的活动还有更多的参加机会。

这种贪心策略保证了我们能够参加最多数量的活动。

代码实现

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        
        priority_queue<int, vector<int>, greater<int>> pq; // 最小堆，存储结束时间
        int i = 0, day = 1, result = 0;
        
        while (i < events.size() || !pq.empty()) {
            // 如果堆为空，跳到下一个活动的开始时间
            if (pq.empty()) {
                day = events[i][0];
            }
            
            // 将今天开始的所有活动加入堆
            while (i < events.size() && events[i][0] <= day) {
                pq.push(events[i][1]);
                i++;
            }
            
            // 移除已经结束的活动
            while (!pq.empty() && pq.top() < day) {
                pq.pop();
            }
            
            // 参加结束时间最早的活动
            if (!pq.empty()) {
                pq.pop();
                result++;
            }
            
            day++;
        }
        
        return result;
    }
};

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        import heapq
        
        events.sort()
        
        pq = []  # 最小堆，存储结束时间
        i = 0
        day = 1
        result = 0
        
        while i < len(events) or pq:
            # 如果堆为空，跳到下一个活动的开始时间
            if not pq:
                day = events[i][0]
            
            # 将今天开始的所有活动加入堆
            while i < len(events) and events[i][0] <= day:
                heapq.heappush(pq, events[i][1])
                i += 1
            
            # 移除已经结束的活动
            while pq and pq[0] < day:
                heapq.heappop(pq)
            
            # 参加结束时间最早的活动
            if pq:
                heapq.heappop(pq)
                result += 1
            
            day += 1
        
        return result

public class Solution {
    public int MaxEvents(int[][] events) {
        Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));
        
        var pq = new PriorityQueue<int, int>(); // 最小堆，存储结束时间
        int i = 0, day = 1, result = 0;
        
        while (i < events.Length || pq.Count > 0) {
            // 如果堆为空，跳到下一个活动的开始时间
            if (pq.Count == 0) {
                day = events[i][0];
            }
            
            // 将今天开始的所有活动加入堆
            while (i < events.Length && events[i][0] <= day) {
                pq.Enqueue(events[i][1], events[i][1]);
                i++;
            }
            
            // 移除已经结束的活动
            while (pq.Count > 0 && pq.Peek() < day) {
                pq.Dequeue();
            }
            
            // 参加结束时间最早的活动
            if (pq.Count > 0) {
                pq.Dequeue();
                result++;
            }
            
            day++;
        }
        
        return result;
    }
}

var maxEvents = function(events) {
    events.sort((a, b) => a[0] - b[0]);
    
    const pq = new MinPriorityQueue(); // 最小堆，存储结束时间
    let i = 0, day = 1, result = 0;
    
    while (i < events.length || !pq.isEmpty()) {
        // 如果堆为空，跳到下一个活动的开始时间
        if (pq.isEmpty()) {
            day = events[i][0];
        }
        
        // 将今天开始的所有活动加入堆
        while (i < events.length && events[i][0] <= day) {
            pq.enqueue(events[i][1]);
            i++;
        }
        
        // 移除已经结束的活动
        while (!pq.isEmpty() && pq.front().element < day) {
            pq.dequeue();
        }
        
        // 参加结束时间最早的活动
        if (!pq.isEmpty()) {
            pq.dequeue();
            result++;
        }
        
        day++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，每个活动最多进出堆一次，堆操作为 O(log n)
空间复杂度O(n)最坏情况下所有活动都在堆中

相关题目