java - 在一组日期中查找时间空间

Question

我带着一个问题来到这里，我想分享一下，我希望任何人都可以帮助我解决这个问题。我会尽可能清楚地描述问题。问题如下。

我有一个 java 程序，有一个接收一组日期的方法 (java.util.Date)。

| start    end  |
| date1    date1|
<--------------->
|       | start        end  |     |                   |
|       | date2        date2|     |                   |
|       <------------------->     |                   |
|                                 | start        end  |
|                                 | date3        date3|
|                                 <------------------->

在上面的示例中，我们有三个日期，前两个日期相交，但开始日期 3 在结束日期 2 之后。对于我的业务规则，这是一个时间空间。

现在考虑下一个场景。

| start    end  |
| date1    date1|
<--------------->
|       | start        end  |     |                   |
|       | date2        date2|     |                   |
|       <------------------->     |                   |
|                                 | start        end  |
|                                 | date3        date3|
|                                 <------------------->   
|  |                                                      |
|  | start                                           end  |
|  | date4                                           date4|
|  <------------------------------------------------------>

在这种情况下，即使 end-date2 和 start-date3 之间有一个时间空间，也认为它不存在时间空间，因为 start-date4 和 end-date4 之间的时间覆盖了这个空间.

如果有一个或多个时间空间，我想检索 true，否则我将返回 false。

我尝试过的唯一方法是循环每个开始/结束关系，比较结束日期​​ 1 与开始日期 2 与开始日期 3 等等……这不是我想要应用的。

如果有其他想法，欢迎大家提出。如果您需要更多信息，我会添加。谢谢。

Answer 1

这个问题有一个非常简单的算法。

1. 创建一个起始值数组和一个单独的结束值数组。
2. 对两个数组进行排序(独立)。

3. 将 InRange 设置为 0。现在按合并顺序扫描两个数组；确保如果值相同，则在起始值之前使用相同的值执行所有结束值。对于扫描中的每个值:

   一个。如果它来自结束值数组:递减 InRange。如果 InRange 现在为 0，则您已找到“时间空间”的起点。

   如果它来自起始值数组:如果 InRange 为 0，则您已找到“时间空间”的结束。无论如何，增加 InRange。

上述算法是为半开区间设计的，其中最终值实际上不包含在区间中。对于日期，您应该假装开始日期实际上是该日期之前的午夜，而结束日期实际上是该日期之后的午夜(因此它与第二天的开始日期相同)。这会影响您按顺序扫描合并数组的方式。如果在您的问题中，日期范围包含，您只需将每个结束日期加 1。

为了清楚起见，在您的第二个示例中，两个数组将是:

1. 开始日期 1、开始日期 4、开始日期 2、开始日期 3
2. 结束日期 1、结束日期 2、结束日期 3、结束日期 4

第3步的处理顺序为:

• 开始日期 1、开始日期 4、开始日期 2、结束日期 1、开始日期 3、结束日期 3、结束日期 4。

您实际上不必创建两个单独的排序数组。您可以对单个数组中的所有端点(作为端点)进行排序，在其中将每个数据标记为开始或结束。 (理想情况下，对于同一个 X，您希望确保结束 X 在开始 X 之前。否则，该算法偶尔会产生零长度的“时间空间”范围，您必须忽略它。)