[路飞]_leetcode-1353-最多可以参加的会议数目

「这是我参与2022首次更文挑战的第23天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

给你一个数组 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 <= 105
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 105

解题思路

首先我们思考一个问题，如何才能尽可能多的参加会议？

答案是如果两个会议的开始时间相同，应该优先参加结束时间早的，因为结束时间晚的会议我们有更多的天数可以使用。

同理，如果两个会议的结束时间相同，则应该优先利用更早的天数把开始时间更早的会议参加掉。

所以我们可以对会议列表进行排序，优先按照结束时间从早到晚排序，如果结束时间相同，则开始时间更早的会议排在前面，优先参加。

为什么不能优先按照开始时间升序排序，然后如果开始时间相同，再按照结束时间升序排序呢？

是因为有些会议开始时间早，但是结束时间晚，此时如果我们先把他们处理了，会导致一些开始时间晚于它们，结束时间早于它们的会议没有时间参加，无法达到参加最多会议的目的。

接下来我们遍历排序后的会议，从早到晚判断会议时间内的每一天是否空闲，找到第一个空闲的天数，如果该天数在会议时间内，则当前会议可以参加，记录可参加会议数量，并将当前天数标记为已占用。

这样的思路是没有问题的，但是因为查找可参加会议的天数效率太低了，会导致超出时间限制。

所以我们要思考如何加速或者说快速查找当前会议开始时间后面的第一个空闲天数？

其实这样的一个问题类似于连通关系问题，如果当前天数已经被使用了，我们标记下一个空闲天数是下一天，而这个标记应该同时给到当前天数之前连续被占用的天数，所以可以抽象化为一个连通关系，连通关系内的天数共同记录后面第一个空闲天数。

涉及到维护这种连通关系的问题，我们可以使用并查集来做。如果你对并查集还不了解的话，可以去看我这篇文章 《并查集》，这里我们不再做详细讲述。

所以本题完整解题思路如下： 对会议按照结束时间降序排序，如果结束时间相同，则按开始时间升序排序

创建并查集维护当前天数后面第一个空闲天数

遍历排序后的会议列表，获取会议开始时间后面的第一个空闲天数，如果该天数不晚于结束时间，则当前会议可以参加，记录会议数量，更新当前空闲天数后的第一个空闲天数为下一天。因为当前数据维护在并查集，则与当前空闲天数连通的被占用天数对应的下一个空闲时间都会被更新为当前空闲天数的下一天。

代码实现

// 并查集
class UnionFind {
  constructor(n){
    this.list = Array(n)
    for(let i = 0;i<n;i++){
      this.list[i] = i;
    }
  }
  // 查找
  find(x){
    if(this.list[x]===x) return x
    // 路径压缩
    this.list[x] = this.find(this.list[x])
    return this.list[x]
  }
  // 合并
  merge(a,b){
    const rootA = this.find(a),
    rootB = this.find(b)
    this.list[rootA] = rootB
  }
}
var maxEvents = function(events) {
  // 对会议排序，结束时间晚的排在后面，结束时间相同，开始时间早的排在前面
  events.sort((a,b) => a[1]===b[1]?a[0]-b[0]:a[1]-b[1])
  // 初始化并查集，长度为最晚天数+1
  const uf = new UnionFind(events[events.length-1][1]+1)
  // 初始化结果值
  let res = 0
  // 遍历排序后的会议列表
  for(let i = 0;i<events.length;i++){
    // 获取会议开始结束天数
    const [a,b] = events[i],
    // 获取开始时间在并查集中对应的未使用天数
    day = uf.find(a)
    // 如果该天数可以参加当前会议，则可参加会议+1，更新并查集当前天数为下一天
    if(day<=b) uf.merge(day,day+1),res++
  }
  return res
};
复制代码

至此我们就完成了 leetcode-1353-最多可以参加的会议数目

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻