难度: Medium
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
示例 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 <= 105events[i].length == 21 <= startDayi <= endDayi <= 105运行时间: 164 ms
内存: 49.3 MB
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
# 对于每个空闲时间，寻找可以参加的，结束时间最早的会议
events.sort(key=itemgetter(0))
ans = 0
i = 0
q = []
n = len(events)
today = -1
while i < n:
today = max(today, events[i][0])
while i < n and events[i][0] <= today:
heappush(q, events[i][1])
i += 1
while q:
end = heappop(q)
if end >= today:
today += 1
while i < n and events[i][0] <= today:
heappush(q, events[i][1])
i += 1
ans += 1
return ans
此题解采用贪心算法和优先队列（最小堆）来解决问题。首先，将会议按照开始时间进行排序。使用一个优先队列来存储当前可以参加的会议的结束时间。对于每一天，从优先队列中选择结束时间最早的会议参加。这样做可以最大限度地留下空间为后续的会议。如果当前最早结束的会议已经不能参加（即结束时间小于当前日期），则将其从队列中移除。重复此过程，直到所有会议都被处理或参加。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
# Sort events based on their start time
events.sort(key=itemgetter(0))
ans = 0 # This will hold the maximum number of events one can attend
i = 0 # Pointer to iterate over events
q = [] # Min-heap to store end times of the events
n = len(events) # Total number of events
today = -1 # Current day, initialized to an invalid value
while i < n:
# Update current day to the maximum of itself and the current event's start day
today = max(today, events[i][0])
# Add all events that start on or before 'today' to the heap
while i < n and events[i][0] <= today:
heappush(q, events[i][1])
i += 1
# Attempt to attend events until the heap is empty
while q:
# Pop the event with the earliest end day
end = heappop(q)
# If the event is still valid
if end >= today:
today += 1 # Attend the event and move to the next day
# Add new events that can now be attended
while i < n and events[i][0] <= today:
heappush(q, events[i][1])
i += 1
ans += 1 # Increment the count of attended events
return ans
在代码中，`today`变量代表当前处理的日期。设置`today = max(today, events[i][0])`的目的是确保`today`不会回到过去，而是始终处于当前正在处理的事件的起始日期或之后的日期。这样的处理逻辑有以下几个作用： 1. **连续性保障**：确保在处理事件时，日期总是从一个事件的开始日期向后逐日推进，避免日期跳跃带来的逻辑错误。 2. **有效性维护**：通过将`today`设置为当前事件的开始日期或已经达到的日期中的较大者，可以避免选择已经过期的事件（即那些结束日期小于当前`today`的事件），因此可以更有效地管理时间和参加更多有效的会议。 3. **优化会议参加次数**：此逻辑确保了每次处理时`today`都尽可能小，同时不会小于任何未处理事件的开始日期，这有助于最大化参加会议的数量，因为可以尽早开始处理每个时间段内的事件。