algorithm - 召开此 session 最少需要多少天？

我是一个IT人员/数学怪人，帮助组织一个会议会议期间活动的时间（而不是日期）已定下来例如，我们知道某一天下午1点到3点会发生某一事件我正在尝试编写一个脚本，它决定了我们可以运行会议的最少天数，并且没有重叠的事件。
所有事件都发生在一天之内；没有任何事件的时间超过上午12点或跨越几天。
我对这个问题的第一次尝试是将它建模为一个无向图。我们可以将事件表示为顶点，两个顶点之间的一条边表示两个事件重叠然后，问题被简化为找到图的最小色数-在确保每个边的端点颜色不同的情况下，给顶点上色所需的最少颜色数。
然而，我无法开发一个有效的动态规划算法，在多项式时间内运行，以计算色数。
还有其他线索吗这似乎是一个NP完全问题，但我敢打赌，我们可以用一个聪明的时空权衡，即动态规划，在多项式时间内解决它。

最佳答案

由于您的图是一个interval graph的问题，所以对于一般的图，使用扫描线算法更容易解决。假设您的事件表示为元组(s_i, f_i)，其中s_i是事件的开始时间，f_i是完成时间（均以小时为单位）。
然后可以使用以下算法：

events := union of {(f_i, -1), (s_i, 1)} for all i
sort events lexicographically
answer := 0
count := 0
for (time, c) in events:
    count += c
    answer := max(answer, count)

return answer

时间复杂度：O(n log n)或甚至O(n)如果我们假设有一个有限的可能的次数（在实践中可能是这样的情况）。

关于algorithm - 召开此 session 最少需要多少天？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22121577/