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

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

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

现在我需要检查重叠日期的最大计数。所以在这个例子中，我们得到了最多 3 个重叠日期(d1、d2、d3)。考虑一下，可以有 0 到 n 个日期。

你能帮我完成这个任务吗？提前谢谢你。

更新

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

输出：重叠日期(作为 MyCustomDate 列表)

每个时间跨度都包括一个 LocalDateTime 类型的起点和终点，其中包含小时和秒。

我的回答将考虑：

给定 (d3， d5) 不重叠 =>重叠(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)也只计算(d2，d3)用于d1检查)并测试每个startDate和endDate。

您可以简单地为每个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。我将保留此答案，因为它 (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。在我的问题中讨论了生成一个新映射，其值是原始映射中集合的计数，通过生成映射到其集合值中元素计数的每个键的新映射来报告多映射，我从 Answer by 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-13=3， 2019-03-13=3， 2019-03-08=3， 2019-03-09=3， 2019-03-10=3， 2019-03-11=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=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-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-13=3， 2019-03-08=3， 2019-03-09=3， 2019-03-10=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-11=3， 2019-04-07=3， 2019-04-08=3， 2019-04-09=3， 2019-04-11=3， 2019-04-11=3， 2019-04-07=3， 2019-04-08=3， 2019-04-09=3， 2019-04-11=3， 2019-04-11=3， 2019-04-07=3， 2019-04-08=3， 2019-04-09=3， 2019-04-10=3， 2019-04-11=3， 2019-04-11=3， 2019-04-11=3， 2019-04-07=3， 2019-04-08=3， 2019-04-09=3， 2019-04-10=3， 2019-04-11=3， 2019-04-11=3， 2019-04-11=3， 2019-04-07=3， 2019-04-08=3， 2019-04-09=3， 2019-019-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 );
}
}

此时存在的其他 2 个答案都是O(n²)，对所有事件进行笛卡尔连接。这个答案显示了一种具有O(n log n)时间复杂度的替代方法。

我们所做的是建立一个有序的日期列表，并为每个日期注册在该日期开始和结束的范围数。它可以存储为单个数字，例如，如果一个范围结束 (-1) 并且 3 个范围开始 (+3)，则日期的增量为 +2。

基本上，每个事件实际上是 2 个事件，一个开始事件和一个结束事件。

然后，我们按日期顺序迭代列表，更新运行总计，并记住最大运行总计。

有几种方法可以对其进行编码。我将使用常规循环，而不是流，并且由于问题说每个日期都有一个低至毫秒的起点和终点，我们将使用一个具有两个Instant字段的DateRange对象。

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));
}

完整代码

相关内容

最新更新

热门标签：