2023-07-20：假设一共有M个车库，编号1~M，时间点从早到晚是从1~T， 一共有N个记录，每一条记录如下{a, b, c

2023-07-20：假设一共有M个车库，编号1 ~ M，时间点从早到晚是从1 ~ T，

一共有N个记录，每一条记录如下，

表示一辆车在b时间点进入a车库，在c时间点从a车库出去，

一共有K个查询，每个查询只有一个数字X，表示请问在X时刻，

有多少个车库包含车的数量>=3，请返回K个查询的答案。

1

1

大厂笔试面经帖子。

答案2023-07-20：

算法1（getAns1）的大体过程如下：

1.遍历所有记录，找到最大时间点 maxT。

2.将每个车库和每个时间点的数量初始化为0。

3.遍历记录，对于每条记录，获取车库编号 s、进入时间 l、离开时间 r，将该时间段内车库 s 的数量加1。

4.遍历查询，对于每个查询时间点 t，统计数量大于等于3的车库数目。

5.返回所有查询的结果。

算法2（getAns2）的大体过程如下：

1.遍历所有记录和查询，将时间点按照从小到大的顺序存储到数组 times 中，并记录每个时间点的排名。

2.对于每条记录，更新记录的起始时间和结束时间为对应的排名。

3.根据车库编号对记录进行排序。

4.创建一个线段树数据结构，并初始化。

5.遍历记录，将统计数量大于等于3的时间段加入到线段树中。

6.遍历查询，使用线段树查询对应时间点的结果。

7.返回所有查询的结果。

两种算法实现的是相同的功能，但是基于不同的数据结构和算法思路。算法1使用二维数组 stores 来统计每个车库和时间点的数量，而算法2使用线段树来高效地统计数量大于等于3的时间段。

算法1的总时间复杂度是O(n + m)，总空间复杂度是O(maxT * K + m)。

算法2的总时间复杂度是O((n + m) log(n + m) + n log n + maxT * log(maxT) + (n + m) log(maxT))，总空间复杂度是O(n + m + maxT)。

go完整代码如下：

在这里插入图片描述