Check if dates are overlapping and return the maximum count

Question

I've multiple dates with start and end. These dates could be like follows:

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

Now I need to check the maximum count of overlapping dates. So in this example, we got maximum 3 overlapping dates (d1, d2, d3). Consider, that there can be 0 to n dates.

Can you help me with this task? Thank you in advance.

UPDATE

Input: List of Java-Dates with start and end point, for example List, where MyCustomDate contains start and end date

Output: Overlapping dates (as List of MyCustomDate)

Each time span includes a start and end point of type LocalDateTime with hours and seconds.

Answer 1

My answer will consider:

• Given (d3, d5) not overlapping => overlap(d1,d3,d5) = 2 as at a given time only two dates will overlap.

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

We sum each overlapping date (even itself as otherwise (d1, d2, d3) would only count (d2, d3) for d1 check) and test each startDate & endDate.

Answer 2

You could simply generate all events between startDate and endDate for each Event (granularity by a day) and compute a Map, where key is LocalDate(as an individual day) and value is the number of times this date was seen:

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

Answer 3

The other 2 answers that exist at this time are both O(n²), doing a Cartesian Join of all the events. This answer shows an alternative approach with a O(n log n) time complexity.

What we do is that we build an ordered list of dates, and register for each date how many ranges starts and ends on that date. It can be stored as a single number, e.g. if a range ends (-1) and 3 ranges start (+3), the delta for the date is +2.

Basically, each event is actually 2 events, a start event and an end event.

Then we iterate the list, in date order, updating a running total, and remember the max running total.

There are a couple of ways to code that. I'm gonna use regular loops, not streams, and since question says that each date has a start and end point down to milliseconds, we'll go with an DateRange object with two Instant fields.

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

Test

//       ....:....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

The above test was simplified to use LocalDate instead of Instant, by adding a helper constructor:

public DateRange(LocalDate start, LocalDate end) {
    this(start.atStartOfDay().toInstant(ZoneOffset.UTC),
         end.atStartOfDay().toInstant(ZoneOffset.UTC));
}

Answer 4

This Question originally asked for dates. After Answers were posted, the Question was changed to ask for LocalDateTime. I’ll leave this Answer posted, as it (a) answered the Question as originally posted, and (b) might be helpful to others.

---

The other Answers look interesting and possibly correct. But I find the following code easier to follow and to verify/debug.

Caveat: I do not claim this code is the best, the leanest, nor the fastest. Frankly, my attempt here was just an exercise to push the limits of my own understanding of using Java streams and lambdas.

Do not invent your own class to hold the start/end dates. The ThreeTen-Extra library provides a LocalDateRange class to represent a span-of-time attached to the timeline as a pair of java.time.LocalDate objects. LocalDateRange offers several methods for:

• Comparison such as abuts and overlaps.
• Factory methods such as union and intersection.

We can define the inputs using the convenient List.of methods in Java 9 and later, to make an unmodifiable 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.
        );

Determine the overall range of dates involved, the very first start and the very last end.

Keep in mind that we are dealing with a list of date-ranges (LocalDateRange), each of which holds a pair of date (LocalDate) objects. The comparator is comparing the starting/ending LocalDate object stored within each LocalDateRange, to get min or max. The get method seen here is getting a LocalDateRange, so we then call getStart/getEnd to retrieve the starting/ending LocalDate stored within.

LocalDate start = dateRanges.stream().min( Comparator.comparing( localDateRange -> localDateRange.getStart() ) ).get().getStart();
LocalDate end = dateRanges.stream().max( Comparator.comparing( localDateRange -> localDateRange.getEnd() ) ).get().getEnd();

Make a list of all the dates within that interval. The LocalDate#datesUntil method generates a stream of LocalDate objects found between a start and end pair of dates. Start is inclusive, while the ending is exclusive.

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

For each of those dates, get a list of the date-ranges 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. We want a count of each List we put into the map above. Generating a new map whose values are the count of a collection in an original map is discussed on my Question, Report on a multimap by producing a new map of each key mapped to the count of elements in its collection value, where I pulled code from 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
                        )
                );

Unfortunately, there seems to be no way to get a stream to filter more than one entry in a map by maximum value. See: Using Java8 Stream to find the highest values from map.

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

Dump to console.

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

Short results.

[Caveat: I have not manually verified these results. Use this code at your own risk, and do your own verification.]

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}

Full code

For your copy-paste convenience, here is an entire class to run this example code.

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