队列算法练习

本文最后更新于：2024年5月11日下午

队列在算法中有很多巧妙应用，本文记录 LeetCode 队列相关题目。

1353. 最多可以参加的会议数目

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。

请你返回你可以参加的最大会议数目。

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort(reverse=True)
        pq = []
        p = 0
        counter = 0
        while True:
            if not pq:
                if  not events:
                    break
                else:
                    p = events[-1][0]
            # 添加事件
            while events and events[-1][0] == p:
                heapq.heappush(pq, events.pop()[1])

            # 开会
            while pq:
                finish_date = heapq.heappop(pq)
                if p <= finish_date:
                    counter += 1
                    break
            p += 1

        return counter