5

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.

Improve this question
9
  • What is your input and output look like ? Commented Jan 11, 2021 at 13:05
  • Does the data fit into memory? How are you representing each period? Do you have to support half open periods e.g. no end date? Commented Jan 11, 2021 at 13:06
  • I've update my question. Commented Jan 11, 2021 at 13:10
  • For inclusive ranges, I can think of a O(n^2) solution. Not sure about edge cases though. First sort the ranges by their starts. For each range r in the sorted list, check how many of the ranges does the start of r fall in. Find the max. Commented Jan 11, 2021 at 13:11
  • 1
    @IQbrod I got the solution using LocalDateTime by just replacing it in your code. Thank you! Commented Jan 14, 2021 at 11:08

4 Answers 4

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

No need to invent your own class. See LocalDateRange in the ThreeTen-Extra library. That project is led by the same man who led the java.time classes (JSR 310) and its predecessor Joda-Time, Stephen Colebourne. LocalDateRange offers several comparison methods including: intersection, overlaps, isBefore/isAfter, abuts, and more.
@BasilBourque it's a nice lib but you rely on range.contains() to determine if LocalDateRange is inclusive or exclusive, whereas I rely on my date comparison stored in overlap().
For comparing a pair of date-ranges, see the overlaps method: LocalDateRange#overlaps​( LocalDateRange other ).
Given d1 = new Event(LocalDate.of(2019,1,1), LocalDate.of(2019,5,1)); and d5 = new Event(LocalDate.of(2018,12,1), LocalDate.of(2019,1,1)); what if endDate is exclusive such as overlap(d1,d5) = 0 ? You can't because you rely the method given above.
Both java.time and ThreeTen-Extra are thread-safe by design, using immutable objects. Specifically, the LocalDateTime class Javadoc declares: This class is immutable and thread-safe.
|
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()
    );
Improve this answer

2 Comments

How can I achieve this using LocalDateTime with hours and seconds?
@Marcel don't get me wrong, but the mere fact that you ask this question means you did not really understood what this is supposed to do. anyway: replace : date -> date.plusDays(1) with date -> date.plus(1, ChronoUnit.SECONDS)
2

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 );
    }
}
Improve this answer

6 Comments

Is thiss also possible using LocalDateTime instead if LocalDate?
the main problem of this is datesUntil, which means the granularity is an actual day.
@Marcel No, this code is for dates. You were asking for dates when I wrote this Answer. Then you changed your Question to LocalDateTime. You should not be changing the nature of your Question after Answers have been written. Put more effort into preparing your Question before you post. It is quite rude of you to waste our time authoring Answers that later look senseless and off-topic.
@Eugene My Answer’s granularity of an actual day was a solution, not a problem, to the original version of this Question. The author later changed the Question to ask for LocalDateTime.
"You were asking for dates when I wrote this Answer" Then you didn't read the question, because more than 9 hours before this answer was posted, the question was updated with "down to milliseconds" clarification, clearly stating that the question was for full timestamps, not for dates only. --- Even if there is only e.g. 2 date ranges, but they cover e.g. 3 years, the code will process 1000+ days. The code doesn't scale well. --- I certainly don't find the 40+ lines of code for the main logic to be "easier to follow and to verify/debug" than the 10 lines of main logic code in my answer.
|
2

The other 2 answers that exist at this time are both O(n2), 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));
}
Improve this answer

1 Comment

Stackoverflow at its finest. An amazingly interesting answer, totally ignored. By far, the best and smartest from all here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.