最多可以参加的会议数目

记住这句:每天先把开始的会议结束日入堆,清掉过期的,再参加堆顶,也就是结束日最早的那场。最快过期的优先抢,这就是贪心的关键。

贪心为什么对:结束早的不抢就过期,结束晚的后面还能补。先救最快过期的,总数不会更差。

第一步:把会议按开始日从早到晚排序,排序后是 [[1,4], [1,1], [2,2], [3,4], [4,4]]。堆现在是空的,从最早的开始日往后扫每一天。

堆空了、还有会议没处理,把「今天」跳到下一场最早的开始日 day=1,从这天继续安排。

来到第 1 天。堆现在是空的,先把今天开始的会议入堆。 接下来:把开始日 ≤ 1 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。

会议1 [1,4] 的开始日 ≤ 今天 day=1,已经开了,把它的结束日 4 丢进小根堆。堆会自动把结束最早的浮到堆顶。

会议2 [1,1] 的开始日 ≤ 今天 day=1,已经开了,把它的结束日 1 丢进小根堆。堆会自动把结束最早的浮到堆顶。

今天 day=1 看堆顶:结束日 1,这是当前所有能参加的会议里结束最早的一场,就参加它。

参加完结束日 1 的那场,已参加 ans=1。今天用掉了,把「今天」推进一天到 day=2,继续处理剩下的会议。

来到第 2 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 2 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。

会议3 [2,2] 的开始日 ≤ 今天 day=2,已经开了,把它的结束日 2 丢进小根堆。堆会自动把结束最早的浮到堆顶。

今天 day=2 看堆顶:结束日 2,这是当前所有能参加的会议里结束最早的一场,就参加它。

参加完结束日 2 的那场,已参加 ans=2。今天用掉了,把「今天」推进一天到 day=3,继续处理剩下的会议。

来到第 3 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 3 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。

会议4 [3,4] 的开始日 ≤ 今天 day=3,已经开了,把它的结束日 4 丢进小根堆。堆会自动把结束最早的浮到堆顶。

今天 day=3 看堆顶:结束日 4,这是当前所有能参加的会议里结束最早的一场,就参加它。

参加完结束日 4 的那场,已参加 ans=3。今天用掉了,把「今天」推进一天到 day=4,继续处理剩下的会议。

来到第 4 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 4 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。

会议5 [4,4] 的开始日 ≤ 今天 day=4,已经开了,把它的结束日 4 丢进小根堆。堆会自动把结束最早的浮到堆顶。

今天 day=4 看堆顶:结束日 4,这是当前所有能参加的会议里结束最早的一场,就参加它。

参加完结束日 4 的那场,已参加 ans=4。今天用掉了,把「今天」推进一天到 day=5,继续处理剩下的会议。

来到第 5 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 5 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。

堆顶结束日 4 < 今天 day=5,这场已经过期、再也赶不上了,直接从堆里弹掉、不计入答案。

所有会议都处理完、堆也空了。整趟下来一共参加了 4 场,和开头说的答案 4 一致。回头看:我们没有暴力枚举安排,只是「每天入堆、清过期、抢结束最早的一场」,贪心一遍就拿到最优解。

单场必为 1、同一天只能参加一场、长跨度会议留到后面、堆空要跳天,这些边界想清就稳。

两个高频追问:为什么逐天推进、以及天数范围很大时为何仍高效。