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. 将范围中的设置为0。现在按合并顺序扫描两个阵列；确保如果值相同，则使用相同的值在开始值之前执行所有结束值。对于扫描中的每个值：

   a.如果它来自结束值数组：范围中的减量。如果范围中的现在为0，则您已找到“时间空间”的开始

   b.如果它来自起始值数组：如果InRange为0，则您已经找到了“时间空间”的end。无论如何，在范围中增加

上述算法是为半开区间设计的，其中终点实际上不包括在区间中。对于日期，您应该假设开始日期实际上是日期前的午夜，而结束日期实际上是日期后的午夜（因此它与第二天的开始日期相同）。这会影响按顺序扫描合并阵列的方式。如果您的问题中的日期范围是包含，您可以在每个结束日期中添加1

为了清楚起见，在第二个示例中，两个阵列将是：

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

步骤3中的处理顺序为：

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

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

Answer 2

好吧，这是一个非常“奇怪”的想法，但看看这个“概念”是否更好

基本上，这个想法是将所有重叠的日期尽可能地合并为几个“范围”，这意味着，在第一个示例中，您将得到两个不同的范围（开始日期1到结束日期2和（开始日期3到结束日期3），在第二个示例中，您将得到一个（开始日期1到结束日期4）

因此，如果集合只有一个不同的范围，那么就没有间隙，换句话说，就是这样

import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;

public class TestDateRanges {

    public static void main(String[] args) {
        try {
            List<Date[]> dates = new ArrayList<>(
                    Arrays.asList(
                            new Date[][]{
                                {makeDate("1.1.2015"), makeDate("5.1.2015")},
                                {makeDate("3.1.2015"), makeDate("10.1.2015")},
                                {makeDate("15.1.2015"), makeDate("20.1.2015")},}
                    )
            );

            Collections.sort(dates, new Comparator<Date[]>() {
                @Override
                public int compare(Date[] o1, Date[] o2) {
                    return o1[0].compareTo(o2[0]);
                }
            });

            List<Date[]> ranges = new ArrayList<>(dates.size());
            Date[] baseRange = null;
            for (Date[] range : dates) {
                if (baseRange == null) {
                    baseRange = range;
                    ranges.add(baseRange);
                } else if ((baseRange[0].before(range[0]) || baseRange[0].equals(range[0])) && (baseRange[1].after(range[0]) || baseRange[1].equals(range[0])) {
                    System.out.println("> Overlap " + format(baseRange) + " <-> " + format(range));
                    if (range[1].after(baseRange[1])) {
                        baseRange[1] = range[1];
                    }
                } else {
                    System.out.println("> Out of range " + format(baseRange) + " >-< " + format(range));
                    baseRange = range;
                    ranges.add(baseRange);
                }
            }

            System.out.println("Has " + ranges.size() + " distinct ranges");

            for (Date[] range : ranges) {
                System.out.println(format(range));
            }
        } catch (ParseException exp) {
            exp.printStackTrace();
        }
    }

    public static final DateFormat FORMAT = new SimpleDateFormat("d.M.yyyy");

    protected static final Date makeDate(String value) throws ParseException {
        return FORMAT.parse(value);
    }

    private static String format(Date[] baseRange) {
        return FORMAT.format(baseRange[0]) + "->" + FORMAT.format(baseRange[1]);
    }

    private static Date[] makeDateRange(String from, String to) throws ParseException {
        return new Date[]{makeDate(from), makeDate(to)};
    }

}

哪个输出

> Overlap 1.1.2015->5.1.2015 <-> 3.1.2015->10.1.2015
> Out of range 1.1.2015->10.1.2015 >-< 15.1.2015->20.1.2015
Has 2 distinct ranges
1.1.2015->10.1.2015
15.1.2015->20.1.2015

现在，如果我将设置更改为

List<Date[]> dates = new ArrayList<>(
        Arrays.asList(
                new Date[][]{
                    {makeDate("1.1.2015"), makeDate("5.1.2015")},
                    {makeDate("3.1.2015"), makeDate("10.1.2015")},
                    {makeDate("15.1.2015"), makeDate("20.1.2015")},
                    makeDateRange("2.1.2015", "25.1.2015")
                }
        )
);

它输出

> Overlap 1.1.2015->5.1.2015 <-> 2.1.2015->25.1.2015
> Overlap 1.1.2015->25.1.2015 <-> 3.1.2015->10.1.2015
> Overlap 1.1.2015->25.1.2015 <-> 15.1.2015->20.1.2015
Has 1 distinct ranges
1.1.2015->25.1.2015

这只是一个概念性的想法，您应该注意，这个示例将更改dates列表中的数据，因此您需要首先确保您拥有数据的副本