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

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。