狗家新鲜面经

Heptapod 发表于 2021-9-2 20:18
积分不够，只看到了第一题会议室的题目。
大概的思路就是初始化全零的向量，然后开始时间点+1，结束时间 ...

你这个就是TreeMap，最简单的方法，还是nlogn

sqzhang17 发表于 2021-9-3 09:59
这道题前缀和是什么算法？ 能说一下吗？

积分不够，只看到了第一题会议室的题目。
大概的思路就是初始化全零的向量，然后开始时间点+1，结束时间点后的一个时间点-1，然后计算前缀和，最大的就是需要的会议室数量。

Heptapod 发表于 2021-9-2 22:18
积分不够，只看到了第一题会议室的题目。
大概的思路就是初始化全零的向量，然后开始时间点+1，结束时间 ...

前缀和不也是得所有时间点排序之后，才能做啊。除非时间点范围比较小才可以用到counting sort O(n)

这个题还能优化吗？我在discussion里也没见过比O(nlog n)更好的做法了。

前缀和复杂度是n

Heptapod 发表于 2021-9-2 17:19
前缀和复杂度是n

这道题前缀和是什么算法？ 能说一下吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

据我所理解，如果还要优化就得有一些提前假设了，如果输入是排好序，可以用离线查询的思路，用哈希表维护会议的增加和删除。这样可以O(N)了。但是用heap就算排序了也是O(NlogN)。

补充内容 (2021-09-03 19:09 +08:00):
更正一下，离线查询也需要排序，所以还不行，可以基于数据假设数据量小用差分数组

楼主能说下怎么优化吗