题目描述

给定一个数组 events，其中 events[i] = [startDayi, endDayi]，表示第 i 个事件从 startDayi 开始，到 endDayi 结束。

你可以在事件 i 的任意一天 d 参加该事件，只要满足 startDayi <= d <= endDayi。在任意一天 d，你只能参加一个事件。

返回可以参加会议的最大数量。

样例

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

算法1

(优先队列) $O(n \log n)$

将所有事件按照它们的开始时间从小到大进行排序。这样我们会从最早能够参加的时间开始处理事件。放进优先队列中，维护一个小顶堆（优先队列），用于存放当前可参加的事件的“结束时间”

Python 代码

class Solution:
    def maxEvents(self, events):
        # 1. 按开始时间升序排序
        events.sort(key=lambda x: x[0])

        min_heap = []

        res = 0
        idx = 0
        n = len(events)

        day = 1

        # 2. 维护min heap
        while idx < n or min_heap:
            while idx < n and events[idx][0] == day:
                heapq.heappush(min_heap, events[idx][1])
                idx += 1

            while min_heap and min_heap[0] < day:
                heapq.heappop(min_heap)

            if min_heap:
                heapq.heappop(min_heap)
                res += 1

            day += 1

        return res