涉及时间间隔及其重叠的问题

Question

我最近遇到了很多涉及时间间隔作为输入的问题.一些时间间隔是重叠的.并且根据您的需要,您必须对输入执行优化,最大化或最小化操作.我无法解决这些问题.事实上,我甚至无法开始考虑这些问题.

这是一个例子:

1. 让我们说,你是一个资源持有者.这种资源可以无限供应.

2. 有些人在特定时间间隔内需要该资源.例如:下午4点到晚上8点

3. 可能存在重叠间隔.例如:下午5点至晚上7点,下午3点至下午6点等.

根据这些间隔及其重叠性质,您必须确定需要多少个不同的这些资源实例.

防爆.输入:

     8 am - 9 am
     8:30 am to 9:15 am
     9.30 am to 1040 am

     In this case, the first two intervals overlap. So two instances of resources will be required. The third interval is not overlapping, so the person with that interval can reuse the resource returned by any of the earlier ones.

因此,在这种情况下,所需的最小资源是2.

我不需要解决方案.我需要一些关于如何解决的指示.有没有解决这些问题的算法？我应该阅读/学习什么.是否有任何可能有用的数据结构.

Answer 1

在任何时刻T重叠的间隔数是小于T的间隔开始时间的数量减去小于或等于T的间隔结束次数.许多这些问题,如上面的特定问题,可以通过放置来解决将开始和结束时间分别分类到排序列表或树中,以便您可以找出有关这些计数如何随时间变化的信息.

例如,要解决此问题,请在单个列表中对开始和结束时间进行排序:

800S, 900E, 830S, 915E, 930S, 1040E

然后排序他们:

800S, 830S, 900E, 915E, 930S, 1040E

遍历列表并计数,每个开始时间加1,每个结束时间减1:

     1     2     1     0      1     0

重叠间隔的最大数量是2.

Answer 2

为解决此类问题,您需要使用的数据结构是Interval Graph.间隔图具有每个间隔的顶点以及与相交的间隔对应的每对顶点之间的边.

以下间隔图对应于示例中的三个间隔的集合:

A: 8:00-9:00
B: 8:30-9:15
C: 9:30-10:40

该数据结构捕获涉及间隔的大多数问题的相关方面,从而有助于有效地解决它们.此外,给定一组间隔(由2元组列表表示),您可以在多项式时间内构造区间图.

在一般图中存在NP难的许多问题,例如找到最大权重独立集或找到最佳着色,可以有效地求解区间图.

要解决您指定的特定问题,首先构造区间图G,同时为每个顶点存储其相应区间的结束时间.同时初始化一组资源R={1},起初只包含一个单一的资源:资源数量1.考虑每个顶点v的G根据其完成时间的排序顺序.分配给v资源编号i ,其中i是R邻居未使用的最小资源v.如果没有这样的资源存在(因为邻居v使用中的所有资源R),插入一个新的资源i=max{R}+1来R并将其分配给v.最佳资源数量(也就是问题的解决方案)是集合的大小R.