涉及时间间隔及其重叠的问题 [英] Problems that involve time intervals and their overlapping

问题描述

我最近遇到了很多问题，其中涉及时间间隔作为输入.一些时间间隔是重叠的.并且取决于您必须对输入执行优化，最大化或最小化操作.我无法解决此类问题.实际上，我什至无法开始思考这些问题.

I have recently came across a lot of questions that involve time intervals as an input. Some of the time intervals are overlapping. And depending upon that you have to perform an optimization, maximization or minimization operation on the input. I am not able to solve such problems. In fact, I am not able to even start thinking on these problems.

这里是一个例子:

1. 让我们说，您是资源持有者.这样的资源可能会无限供应.

1. Let us say, you are a resource holder. There can be an infinite supply of such a resource.

有些人想要在特定时间间隔内使用该资源.例如:下午4点至晚上8点

There are people who want that resource for a particular time interval. For ex: 4 pm to 8 pm

可以有一个重叠的间隔.例如:下午5时至7时，下午3时至6时等等

There can be an overlapping interval. ex: 5 pm to 7 pm, 3 pm to 6 pm etc.

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

Depending upon these intervals, and their overlapping nature, you have to figure out how many distinct instances of these resources are required.

例如输入:

     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.

Hence, in this case, minimum resources required are 2.

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

I don't need a solution. I need some pointers on how to solve. Are there any algorithms that address such questions? What should I read/ study. Are there any data structures that might help.

推荐答案

与任意时刻T重叠的间隔数是间隔开始时间小于T的数量，减去间隔结束时间小于或等于T的数量.通过将开始时间和结束时间分别放入排序的列表或树中，可以解决许多此类问题，例如上面的特定问题，这样您就可以找出有关这些计数随时间变化的信息.

The number of intervals overlapping any time instant T is the number of interval start times less than T, minus the number of interval end times less than or equal to T. Many of these problems, like the specific one above, can be solved by putting the start and end times separately into a sorted list or tree so you can figure out stuff about how these counts change over time.

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

To solve this problem, for example, sort the start and end times in a single list:

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

然后对它们进行排序:

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

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

The run through the list and count, adding 1 for each start time and subtracting one for each end time:

     1     2     1     0      1     0

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

The highest number of overlapping intervals is 2.

这篇关于涉及时间间隔及其重叠的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！