logo标签列表

检查日期是否重叠并返回最大计数

javadatecompare
5

我有多个带有开始和结束日期的日期。 这些日期可能如下所示：

d1:      |----------|
d2:            |------|
d3:        |--------------|
d4:                         |----|
d5:   |----|

现在我需要检查重叠日期的最大计数。

在这个例子中，我们有最多3个重叠日期（d1，d2，d3）。

请注意，可以有0到n个日期。

你能帮助我完成这个任务吗？

提前致谢感谢您。

更新

输入：具有开始和结束点的Java-Date列表，例如List，其中MyCustomDate包含开始和结束日期

输出：

重叠日期（作为MyCustomDate列表）

每个时间跨度均包括带小时和秒的LocalDateTime类型的开始和结束点。

你的输入和输出长什么样？ - Umeshwaran
数据是否适合内存？您如何表示每个时间段？您是否需要支持半开放的时间段，例如没有结束日期？ - Karol Dowbecki
我已经更新了我的问题。 - marc3l
对于包含范围，我可以想到一个O(n^2)的解决方案。不过边缘情况还不确定。首先按它们的起始点对范围进行排序。对于排序后列表中的每个范围r，检查r的起始点落在多少个范围内。找到最大值。 - Sweeper
1
@IQbrod 我已经使用LocalDateTime找到了解决方案，只需在您的代码中进行替换即可。谢谢！ - marc3l
显示剩余4条评论
4个回答
4

我的答案将考虑：

  • 假设（d3，d5）不重叠，则 overlap(d1, d3, d5) = 2，因为在任何时候只有两个日期会重叠。
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.List;

class Event {
    LocalDate startDate; // inclusive
    LocalDate endDate; // inclusive

    Event(LocalDate st, LocalDate end) {
        this.startDate = st;
        this.endDate = end;
    }

    // Getters & Setters omitted
}

public class Main {
    public static void main(String[] args) {
        List<Event> events = new ArrayList<Event>();
        events.add(new Event(LocalDate.of(2019,1,1), LocalDate.of(2019,5,1))); // d1
        events.add(new Event(LocalDate.of(2019,3,1), LocalDate.of(2019,6,1))); // d2
        events.add(new Event(LocalDate.of(2019,2,1), LocalDate.of(2019,7,1))); // d3
        events.add(new Event(LocalDate.of(2019,8,1), LocalDate.of(2019,12,1))); // d4
        // d5 do not overlap d3
        events.add(new Event(LocalDate.of(2018,12,1), LocalDate.of(2019,1,31))); // d5

        Integer startDateOverlaps = events.stream().map(Event::getStartDate).mapToInt(date -> overlap(date, events)).max().orElse(0);
        Integer endDateOverlaps = events.stream().map(Event::getEndDate).mapToInt(date -> overlap(date, events)).max().orElse(0);

        System.out.println(Integer.max(startDateOverlaps, endDateOverlaps));
    }

    public static Integer overlap(LocalDate date, List<Event> events) {
        return events.stream().mapToInt(event -> (! (date.isBefore(event.startDate) || date.isAfter(event.endDate))) ? 1 : 0).sum();
    }
}

我们对每个重叠的日期求和（包括其本身，否则将仅针对d1检查计数(d2, d3)），并测试每个startDate和endDate。
不需要自己编写类。请查看ThreeTen-Extra库中的LocalDateRange。该项目由同一位领导了java.time类（JSR 310）及其前身Joda-Time的Stephen Colebourne领导。LocalDateRange提供了多种比较方法，包括：交集、重叠、isBefore/isAfter、相接等。 - Basil Bourque
@BasilBourque 这是一个不错的库，但你依赖于 range.contains() 来确定 LocalDateRange 是包含还是排除的，而我则依赖于存储在 overlap() 中的日期比较。 - IQbrod
要比较一对日期范围，请参见 overlaps 方法：LocalDateRange#overlaps​( LocalDateRange other )。 - Basil Bourque
给定 d1 = new Event(LocalDate.of(2019,1,1), LocalDate.of(2019,5,1)); 和 d5 = new Event(LocalDate.of(2018,12,1), LocalDate.of(2019,1,1));，如果 endDate 是不包含的，比如 overlap(d1,d5) = 0，那么你不能使用上面提供的方法。 - IQbrod
1
java.time和ThreeTen-Extra都是通过使用不可变对象来设计实现线程安全的。具体而言，LocalDateTime类的Javadoc声明：此类是不可变且线程安全的。 - Basil Bourque
显示剩余3条评论
2
此时存在的另外两个答案都是O(n^2)，需要对所有事件进行笛卡尔积。这个答案提供了一种具有O(n log n)时间复杂度的替代方法。
我们需要建立一个日期有序列表，并为每个日期注册在该日期上开始和结束的范围数量。它可以存储为一个单一数字，例如，如果一个范围结束(-1)且3个范围开始(+3)，则该日期的增量为+2。
基本上，每个事件实际上是两个事件，一个开始事件和一个结束事件。
然后，我们按日期顺序迭代列表，更新运行总数，并记住最大运行总数。
有几种编码方式。我将使用常规循环而不是流，并且由于问题说明每个日期都有毫秒级别的起点和终点，因此我们将使用一个DateRange对象，其中包含两个Instant字段。
static int maxRangeOverlaps(List<DateRange> ranges) {
    Map<Instant, Delta> dateDelta = new TreeMap<>();
    for (DateRange range : ranges) {
        dateDelta.computeIfAbsent(range.getStart(), k -> new Delta()).value++;
        dateDelta.computeIfAbsent(range.getEnd(), k -> new Delta()).value--;
    }
    int total = 0, max = 0;
    for (Delta delta : dateDelta.values())
        if ((total += delta.value) > max)
            max = total;
    return max;
}


public final class DateRange {
    private final Instant start; // inclusive
    private final Instant end; // exclusive

    // Constructor and getter methods here
}


final class Delta {
    public int value;
}

测试

//       ....:....1....:....2....:....3
// d1:      |----------|
// d2:            |------|
// d3:        |--------------|
// d4:                         |----|
// d5:   |----|
List<DateRange> ranges = Arrays.asList(
        new DateRange(LocalDate.of(2021,1, 4), LocalDate.of(2021,1,15)),
        new DateRange(LocalDate.of(2021,1,10), LocalDate.of(2021,1,17)),
        new DateRange(LocalDate.of(2021,1, 6), LocalDate.of(2021,1,21)),
        new DateRange(LocalDate.of(2021,1,23), LocalDate.of(2021,1,28)),
        new DateRange(LocalDate.of(2021,1, 1), LocalDate.of(2021,1, 6)));

System.out.println(maxRangeOverlaps(ranges)); // prints 3

上述测试被简化为使用LocalDate而不是Instant，通过添加一个帮助构造函数：
public DateRange(LocalDate start, LocalDate end) {
    this(start.atStartOfDay().toInstant(ZoneOffset.UTC),
         end.atStartOfDay().toInstant(ZoneOffset.UTC));
}
StackOverflow的精华。一个非常有趣的答案，完全被忽视了。迄今为止，这里最好、最聪明的答案。 - Eugene
2

这个问题最初是要求日期的。在答案发布后，问题被更改为要求LocalDateTime。我将保留此答案，因为它(a)回答了最初发布的问题，(b)可能对其他人有帮助。

其他答案看起来很有趣，也可能是正确的。但我发现以下代码更容易理解和验证/调试。

注意: 我不断言这段代码是最好的、最简洁的或最快的。坦白地说，我在这里的尝试只是为了推动我的Java流和lambda使用理解的极限。

不要发明自己的类来保存开始/结束日期。 ThreeTen-Extra库提供了一个LocalDateRange类，用于表示作为一对java.time.LocalDate对象附加到时间线上的时间跨度。 LocalDateRange提供了几种方法，如：

  • 比较，如abuts和overlaps。
  • 工厂方法，如union和intersection。

我们可以使用Java 9及更高版本中方便的List.of方法定义输入，以创建一个不可修改的LocalDateRange列表。

List < LocalDateRange > dateRanges =
        List.of(
                LocalDateRange.of( LocalDate.of( 2019 , 1 , 1 ) , LocalDate.of( 2019 , 5 , 1 ) ) ,
                LocalDateRange.of( LocalDate.of( 2019 , 3 , 1 ) , LocalDate.of( 2019 , 6 , 1 ) ) ,
                LocalDateRange.of( LocalDate.of( 2019 , 2 , 1 ) , LocalDate.of( 2019 , 7 , 1 ) ) ,
                LocalDateRange.of( LocalDate.of( 2019 , 8 , 1 ) , LocalDate.of( 2019 , 12 , 1 ) ) , // Not connected to the others.
                LocalDateRange.of( LocalDate.of( 2018 , 12 , 1 ) , LocalDate.of( 2019 , 1 , 31 ) )  // Earlier start, in previous year.
        );

确定涉及的日期总范围，最早开始和最晚结束日期。
请注意，我们正在处理日期范围列表（LocalDateRange），每个日期范围包含一对日期对象（LocalDate）。比较器正在比较存储在每个LocalDateRange中的起始/结束LocalDate对象，以获取最小值或最大值。这里看到的get方法正在获取一个LocalDateRange，因此我们随后调用getStart/getEnd来检索存储在其中的起始/结束LocalDate。
LocalDate start = dateRanges.stream().min( Comparator.comparing( localDateRange -> localDateRange.getStart() ) ).get().getStart();
LocalDate end = dateRanges.stream().max( Comparator.comparing( localDateRange -> localDateRange.getEnd() ) ).get().getEnd();

列出该时间间隔内的所有日期。 LocalDate#datesUntil 方法生成一个 LocalDate 对象流，该流包含在开始和结束日期对之间找到的对象。开始日期是包含的，而结束日期是不包含的。

List < LocalDate > dates =
        start
                .datesUntil( end )
                .collect( Collectors.toList() );

对于这些日期中的每一个，获取包含该日期的日期范围列表。
Map < LocalDate, List < LocalDateRange > > mapDateToListOfDateRanges = new TreeMap <>();
for ( LocalDate date : dates )
{
    List < LocalDateRange > hits = dateRanges.stream().filter( range -> range.contains( date ) ).collect( Collectors.toList() );
    System.out.println( date + " ➡ " + hits );  // Visually interesting to see on the console.
    mapDateToListOfDateRanges.put( date , hits );
}

对于这些日期中的每一个，获取包含该日期的日期范围的计数。我们想要上面放入映射的每个List的计数。生成一个新映射，其值是原始映射中集合计数的计数，在我的问题Report on a multimap by producing a new map of each key mapped to the count of elements in its collection value中讨论，我从Syco的答案中提取了代码，请参考。
Map < LocalDate, Integer > mapDateToCountOfDateRanges =
        mapDateToListOfDateRanges
                .entrySet()
                .stream()
                .collect(
                        Collectors.toMap(
                                ( Map.Entry < LocalDate, List < LocalDateRange > > e ) -> { return e.getKey(); } ,
                                ( Map.Entry < LocalDate, List < LocalDateRange > > e ) -> { return e.getValue().size(); } ,
                                ( o1 , o2 ) -> o1 ,
                                TreeMap :: new
                        )
                );

很遗憾，似乎没有办法通过流过滤地图中多个条目的最大值。请参见：使用Java8 Stream从地图中查找最高值。

因此，首先我们找到映射的一个或多个条目中值的最大数。

Integer max = mapDateToCountOfDateRanges.values().stream().max( Comparator.naturalOrder() ).get();

然后，我们筛选只有该数字值的条目，并将这些条目移动到一个新地图中。

Map < LocalDate, Integer > mapDateToCountOfDateRangesFilteredByHighestCount =
        mapDateToCountOfDateRanges
                .entrySet()
                .stream()
                .filter( e -> e.getValue() == max )
                .collect(
                        Collectors.toMap(
                                Map.Entry :: getKey ,
                                Map.Entry :: getValue ,
                                ( o1 , o2 ) -> o1 ,
                                TreeMap :: new
                        )
                );

输出到控制台。

System.out.println( "dateRanges = " + dateRanges );
System.out.println( "start/end = " + LocalDateRange.of( start , end ).toString() );
System.out.println( "mapDateToListOfDateRanges = " + mapDateToListOfDateRanges );
System.out.println( "mapDateToCountOfDateRanges = " + mapDateToCountOfDateRanges );
System.out.println( "mapDateToCountOfDateRangesFilteredByHighestCount = " + mapDateToCountOfDateRangesFilteredByHighestCount );

简短的结果。

[注意: 我没有手动验证这些结果。使用此代码需自行风险评估，并进行自己的验证。]

mapDateToCountOfDateRangesFilteredByHighestCount = {2019-03-01=3, 2019-03-02=3, 2019-03-03=3, 2019-03-04=3, 2019-03-05=3, 2019-03-06=3, 2019-03-07=3, 2019-03-08=3, 2019-03-09=3, 2019-03-10=3, 2019-03-11=3, 2019-03-12=3, 2019-03-13=3, 2019-03-14=3, 2019-03-15=3, 2019-03-16=3, 2019-03-17=3, 2019-03-18=3, 2019-03-19=3, 2019-03-20=3, 2019-03-21=3, 2019-03-22=3, 2019-03-23=3, 2019-03-24=3, 2019-03-25=3, 2019-03-26=3, 2019-03-27=3, 2019-03-28=3, 2019-03-29=3, 2019-03-30=3, 2019-03-31=3, 2019-04-01=3, 2019-04-02=3, 2019-04-03=3, 2019-04-04=3, 2019-04-05=3, 2019-04-06=3, 2019-04-07=3, 2019-04-08=3, 2019-04-09=3, 2019-04-10=3, 2019-04-11=3, 2019-04-12=3, 2019-04-13=3, 2019-04-14=3, 2019-04-15=3, 2019-04-16=3, 2019-04-17=3, 2019-04-18=3, 2019-04-19=3, 2019-04-20=3, 2019-04-21=3, 2019-04-22=3, 2019-04-23=3, 2019-04-24=3, 2019-04-25=3, 2019-04-26=3, 2019-04-27=3, 2019-04-28=3, 2019-04-29=3, 2019-04-30=3}

完整代码

为了方便复制粘贴，这里提供一个完整的类来运行这个示例代码。
package work.basil.example;


import org.threeten.extra.LocalDateRange;

import java.time.LocalDate;
import java.util.*;
import java.util.stream.Collectors;

public class DateRanger
{
    public static void main ( String[] args )
    {
        DateRanger app = new DateRanger();
        app.demo();
    }

    private void demo ( )
    {
        // Input.
        List < LocalDateRange > dateRanges =
                List.of(
                        LocalDateRange.of( LocalDate.of( 2019 , 1 , 1 ) , LocalDate.of( 2019 , 5 , 1 ) ) ,
                        LocalDateRange.of( LocalDate.of( 2019 , 3 , 1 ) , LocalDate.of( 2019 , 6 , 1 ) ) ,
                        LocalDateRange.of( LocalDate.of( 2019 , 2 , 1 ) , LocalDate.of( 2019 , 7 , 1 ) ) ,
                        LocalDateRange.of( LocalDate.of( 2019 , 8 , 1 ) , LocalDate.of( 2019 , 12 , 1 ) ) , // Not connected to the others.
                        LocalDateRange.of( LocalDate.of( 2018 , 12 , 1 ) , LocalDate.of( 2019 , 1 , 31 ) )  // Earlier start, in previous year.
                );


        // Determine first start and last end.
        LocalDate start = dateRanges.stream().min( Comparator.comparing( localDateRange -> localDateRange.getStart() ) ).get().getStart();
        LocalDate end = dateRanges.stream().max( Comparator.comparing( localDateRange -> localDateRange.getEnd() ) ).get().getEnd();
        List < LocalDate > dates =
                start
                        .datesUntil( end )
                        .collect( Collectors.toList() );

        // For each date, get a list of the date-dateRanges containing that date.
        Map < LocalDate, List < LocalDateRange > > mapDateToListOfDateRanges = new TreeMap <>();
        for ( LocalDate date : dates )
        {
            List < LocalDateRange > hits = dateRanges.stream().filter( range -> range.contains( date ) ).collect( Collectors.toList() );
            System.out.println( date + " ➡ " + hits );  // Visually interesting to see on the console.
            mapDateToListOfDateRanges.put( date , hits );
        }

        // For each of those dates, get a count of date-ranges containing that date.
        Map < LocalDate, Integer > mapDateToCountOfDateRanges =
                mapDateToListOfDateRanges
                        .entrySet()
                        .stream()
                        .collect(
                                Collectors.toMap(
                                        ( Map.Entry < LocalDate, List < LocalDateRange > > e ) -> { return e.getKey(); } ,
                                        ( Map.Entry < LocalDate, List < LocalDateRange > > e ) -> { return e.getValue().size(); } ,
                                        ( o1 , o2 ) -> o1 ,
                                        TreeMap :: new
                                )
                        );

        // Unfortunately, there seems to be no way to get a stream to filter more than one entry in a map by maximum value.
        // So first we find the maximum number in a value for one or more entries of our map.
        Integer max = mapDateToCountOfDateRanges.values().stream().max( Comparator.naturalOrder() ).get();
        // Then we filter for only entries with a value of that number, moving those entries to a new map.
        Map < LocalDate, Integer > mapDateToCountOfDateRangesFilteredByHighestCount =
                mapDateToCountOfDateRanges
                        .entrySet()
                        .stream()
                        .filter( e -> e.getValue() == max )
                        .collect(
                                Collectors.toMap(
                                        Map.Entry :: getKey ,
                                        Map.Entry :: getValue ,
                                        ( o1 , o2 ) -> o1 ,
                                        TreeMap :: new
                                )
                        );

        System.out.println( "dateRanges = " + dateRanges );
        System.out.println( "start/end = " + LocalDateRange.of( start , end ).toString() );
        System.out.println( "mapDateToListOfDateRanges = " + mapDateToListOfDateRanges );
        System.out.println( "mapDateToCountOfDateRanges = " + mapDateToCountOfDateRanges );
        System.out.println( "mapDateToCountOfDateRangesFilteredByHighestCount = " + mapDateToCountOfDateRangesFilteredByHighestCount );
    }
}
1
这也可以使用 LocalDateTime 而不是 LocalDate 吗？ - marc3l
这个主要问题在于 datesUntil，它意味着粒度是一整天。 - Eugene
@Marcel 不，这段代码是用于日期的。当我写下这个答案时，你询问的是日期。然后你把问题改成了 LocalDateTime。在回答被写出之后更改问题的性质是不应该的。在发布之前更加努力地准备你的问题。浪费我们的时间来撰写后来看起来毫无意义和离题的答案是相当无礼的。 - Basil Bourque
@Eugene 我的答案以实际天为粒度是对于原始版本的这个问题的一个解决方案，而不是一个问题。作者后来更改了问题，要求使用LocalDateTime。 - Basil Bourque
@BasilBourque 对，我并不打算说反话，只是想提出这个简单的观点。 - Eugene
1
当我写这个答案时，你正在询问日期。那么你没有读清楚问题，因为在此回答发布的9个小时前，问题已经更新了“到毫秒”的澄清，明确说明问题是关于完整时间戳，而不仅仅是日期。即使只有2个日期范围，但它们涵盖了3年，代码也会处理1000多天。该代码不具备良好的可扩展性。我认为主要逻辑中的40多行代码并不比我的答案中的10行主要逻辑代码更易于理解、验证和调试。 - Andreas
2

您可以简单地为每个Event（按天粒度）生成startDate和endDate之间的所有事件，并计算一个Map，其中键是LocalDate（作为单独的一天），值是看到该日期的次数：

long l =
    Collections.max(
            events.stream()
                  .flatMap(x -> Stream.iterate(x.getStartDate(), date -> date.plusDays(1))
                        .limit(ChronoUnit.DAYS.between(x.getStartDate(), x.getEndDate().plusDays(1))))
                  .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
                  .values()
    );
我如何使用LocalDateTime实现带有小时和秒的功能？ - marc3l
@Marcel，不要误解我的意思，但你提出这个问题的事实表明你并没有真正理解这个应该做什么。不管怎样：用 date -> date.plusDays(1) 替换为 date -> date.plus(1, ChronoUnit.SECONDS)。 - Eugene
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接