Set Slice成员算法

Question

这是我本科生CS上的一个漏洞，除了幼稚的方法之外，我从来没有完全弄清楚任何事情。

假设我们将一周分成几分钟(10,080分钟)，我们有从给定分钟开始并持续一段时间的“显示”。

所以在480分钟，我们可能会有一个30分钟的节目。

所以我们有N个节目，每个节目都有开始时间和持续时间，问题是，给定1..10080范围内的某个分钟值，找出它是否在节目中的更好方法是什么，而不是天真地遍历所有这些节目并执行< and >或开始时间的基本树。

我在想，如果有一种聪明的散列算法，可以在上面执行其他聪明的成员资格测试。具有前期插入成本但有效聚合O(1)搜索的内容。我的直觉告诉我应该有一个聪明的方法。

或者，计算机是否足够快，以至于最佳解决方案只是旋转我的轮子，浪费时间？

Answer 1

使用10080位数组，并为每个特定节目标记已使用1的时间。当要检查下一个节目时，只需检查特定分钟是否设置为o(1)