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

问题描述#

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

你可以在满足 startDay_i <= d <= endDay_i中的任意一天 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
示例 3：
输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出：4
示例 4：
输入：events = [[1,100000]]
输出：1
示例 5：
输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出：7
提示：

1 <= events.length <= 10^5

events[i].length == 2

1 <= events[i][0] <= events[i][1] <= 10^5

解题思路#

对于第 \(i\) 天，我们应该在余下的会议中选择：

\[ k=\mathop{\arg\min}_{\texttt{endDay}_j\ge i}^{\texttt{startDay}_j\le i}(\texttt{endDay}_j) \]

import heapq

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        # 倒序排序用完就可以直接弹出
        # 如果正序排序还需要用一个指针记录下标位置
        events.sort(reverse=True)
        L, R = events[-1][0], max(events, key=lambda x: x[1])[1]  # 参加会议的天数范围
        end = []  # 记录所有 startDay <= i 的 endDay
        ans = 0
        for i in range(L, R + 1):
            while events and events[-1][0] == i:  # startDay <= i
                heapq.heappush(end, events[-1][1])
                events.pop()

            while end:
                e = heapq.heappop(end)
                if e >= i:  # 弹出所有过期的会议直到存在第 i 天可以参加的会议
                    ans += 1
                    break
        return ans

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

问题描述#

解题思路#

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