How to Check a Timeperiod Is Overlapping Another Time Period in Java

How to check if time period is overlapping another time period irrespective of AM/PM

Assuming that each interval is within either AM or PM

I am assuming that each interval is either completely within AM (00:00 through 12) or PM (12:00 through 00). I didn’t understand what you meant by “(+/- 30 mins)”, so I have ignored that.

As an aside I consider this an artificial challenge. In the real world 2 AM and 2 PM are not the same, they just happen to have identical representations on a 12 hour clock. Just as a flag pole and a person from Poland are not the same even though they both have the representation “Pole”.

As Sweeper suggested in a comment I am converting each interval to AM (if it was in PM) before comapring.

    LocalTime begin1 = LocalTime.of(1, 0);
    LocalTime end1 = LocalTime.of(3, 0);
    LocalTime begin2 = LocalTime.of(13, 45);
    LocalTime end2 = LocalTime.of(14, 45);

    // Convert interval 1 to AM
    if (begin1.get(ChronoField.AMPM_OF_DAY) == 1) { // PM
        begin1 = begin1.minusHours(12);
        end1 = end1.minusHours(12);
    }
    // validate
    if (end1.isBefore(begin1)) {
        throw new IllegalStateException("end1 " + end1 + " must not be before begin1 " + begin1);
    }
    if (end1.isAfter(LocalTime.NOON)) {
        throw new IllegalStateException("Interval 1 must be completely within either AM or PM");
    }

    // Convert interval 2 to AM
    if (begin2.get(ChronoField.AMPM_OF_DAY) == 1) {
        begin2 = begin2.minusHours(12);
        end2 = end2.minusHours(12);
    }
    // validate
    if (end2.isBefore(begin2)) {
        throw new IllegalStateException("end2 " + end2 + " must not be before begin2 " + begin2);
    }
    if (end2.isAfter(LocalTime.NOON)) {
        throw new IllegalStateException("Interval 2 must be completely within either AM or PM");
    }

    if (end2.isAfter(begin1) && end1.isAfter(begin2)) {
        System.out.println("They overlap");
    } else {
        System.out.println("They do not overlap");
    }

Output from this code is:

They overlap

Corner case: I am accepting an end time of 12:00 (noon) for an AM interval and of 00:00 for a PM interval. LocalTime.minusHours() has cyclic underflow, so subtracting 12 hours from 00:00 gives 12:00.

The code may be simpler and easier to find your way through if you define a TimePeriod class with fields for begin and end, a method for checking overlap and an auxiliary method for converting into AM.

With no restrictions

Edit: Assuming that each interval can be any length from 0 (inclusive) to 24 hours (exclusive) and may cross 00:00, this is somewhat more complicated, but I couldn’t let the challenge rest.

Some observations:

1. If one interval is 12 hours or longer and the other has non-zero length, the two necessarily overlap.
2. If both intervals are shorter than 12 hours, then if they do not overlap, we can go (count) cyclically forward from begin1 through end1 and begin2 to end2 in the order given here and either not cross 12 o’clock or cross 12 once and end up before begin1. If this cycle doesn’t work, then the intervals must overlap somehow.

In code:

public static boolean overlaps(LocalTime begin1, LocalTime end1, LocalTime begin2, LocalTime end2) {
    if (begin1.equals(end1)) { // zero length, cannot overlap anything
        return false;
    }
    if (begin2.equals(end2)) {
        return false;
    }

    // If any interval is 12 hours or longer,
    // the other one is necessarily included, that is, overlaps
    if (is12HoursOrLonger(begin1, end1)) {
        return true;
    }
    if (is12HoursOrLonger(begin2, end2)) {
        return true;
    }

    // Convert all times to AM
    begin1 = toAm(begin1);
    end1 = toAm(end1);
    begin2 = toAm(begin2);
    end2 = toAm(end2);

    // For the two intervals *not* to overlap we must be able to go forward
    // from begin1 through end1 and begin2 to end2 in this order either
    // not crossing 12 or crossing 12 once and ending before or on begin1
    boolean crossed12OClock = false;
    if (end1.isBefore(begin1)) { // to go forward to end1 we are crossing 12 o’clock
        crossed12OClock = true;
    }
    if (begin2.isBefore(end1)) {
        if (crossed12OClock) {
            // crossing 12 for the second time;
            // intervals cannot be in non-overlapping order
            return true;
        }
        crossed12OClock = true;
    }
    if (end2.isBefore(begin2)) {
        if (crossed12OClock) {
            return true;
        }
        crossed12OClock = true;
    }
    if (crossed12OClock) {
        return end2.isAfter(begin1);
    } else {
        return false;
    }
}

This method uses the following two auxiliary methods:

private static boolean is12HoursOrLonger(LocalTime begin, LocalTime end) {
    Duration length = Duration.between(begin, end);
    if (length.isNegative()) {
        length = length.plusDays(1);
    }
    return ! length.minusHours(12).isNegative();
}

private static LocalTime toAm(LocalTime time) {
    return time.with(ChronoField.AMPM_OF_DAY, 0);
}

Let’s try it out using the times from before:

    if (overlaps(begin1, end1, begin2, end2)) {
        System.out.println("They overlap");
    } else {
        System.out.println("They do not overlap");
    }

They overlap

Since the code and the arguments are complicated, make sure to cover the methods thoroughly with unit tests.

Determine Whether Two Date Ranges Overlap

(StartA <= EndB) and (EndA >= StartB)

Proof:

Let ConditionA Mean that DateRange A Completely After DateRange B

_                        |---- DateRange A ------|
|---Date Range B -----|                          _

(True if StartA > EndB)

Let ConditionB Mean that DateRange A is Completely Before DateRange B

|---- DateRange A -----|                        _ 
_                          |---Date Range B ----|

(True if EndA < StartB)

Then Overlap exists if Neither A Nor B is true -

(If one range is neither completely after the other,

nor completely before the other,
then they must overlap.)

Now one of De Morgan's laws says that:

Not (A Or B) <=> Not A And Not B

Which translates to: (StartA <= EndB) and (EndA >= StartB)

---

NOTE: This includes conditions where the edges overlap exactly. If you wish to exclude that,

change the >= operators to >, and <= to <

---

NOTE2. Thanks to @Baodad, see this blog, the actual overlap is least of:

{ endA-startA, endA - startB, endB-startA, endB - startB }

(StartA <= EndB) and (EndA >= StartB)
(StartA <= EndB) and (StartB <= EndA)

---

NOTE3. Thanks to @tomosius, a shorter version reads:

DateRangesOverlap = max(start1, start2) < min(end1, end2)

This is actually a syntactical shortcut for what is a longer implementation, which includes extra checks to verify that the start dates are on or before the endDates. Deriving this from above:

If start and end dates can be out of order, i.e., if it is possible that startA > endA or startB > endB, then you also have to check that they are in order, so that means you have to add two additional validity rules:

(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB)
or:

(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB)
or,

(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB))
or:

(Max(StartA, StartB) <= Min(EndA, EndB)

But to implement Min() and Max(), you have to code, (using C ternary for terseness),:

((StartA > StartB) ? StartA : StartB) <= ((EndA < EndB) ? EndA : EndB)

Check if dates are overlapping and return the maximum count

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.

Calculate duration between multiple date ranges without overlapping date time

Here's my approach:

• by iterating over the rows from the database, create a list of job durations that take the overlaps into account
  
  • if a new row overlaps an existing JobDuration in the list, the existing element will be modified with the new start and/or end date
• this list can now be turned into duration values

Take a look at this code:

class Scratch {

  static final DateTimeFormatter FORMATTER = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss.SSSSSS");

  public static void main(String[] args) {
    List<JobDuration> durations = new ArrayList<>();
    List<JobDuration> newJobs = List.of(
            //commented because it has type=1
            /*JobDuration.of("2022-07-29 08:30:00.414000", "2022-07-29 19:56:33.414000"),*/
            JobDuration.of("2022-07-29 15:30:03.412754", "2022-07-29 15:57:03.965432"),
            JobDuration.of("2022-07-29 15:40:03.414000", "2022-07-29 16:32:03.004323"),
            JobDuration.of("2022-07-29 16:50:03.643231", "2022-07-29 17:35:03.234562")
    );
    newJobs.stream().forEach(d -> addDuration(durations, d));

    Collections.sort(durations, Comparator.comparing(JobDuration::getStart));
    System.out.println(durations);
    durations.stream().map(JobDuration::getDuration).forEach(System.out::println);
  }

  private static void addDuration(List<JobDuration> durations, JobDuration newJdr) {
    if(durations.isEmpty()) {
      durations.add(newJdr);
      return;
    }
    boolean overlap = false;
    for(JobDuration j:durations) {
      //overlaps at the start?
      if(newJdr.start.isBefore(j.start) && newJdr.end.isAfter(j.start)) {
        j.start = newJdr.start;
        overlap = true;
      }
      //overlaps at the end?
      if(newJdr.start.isBefore(j.end) && newJdr.end.isAfter(j.end)) {
        j.end = newJdr.end;
        overlap = true;
      }
      //is completely inside?
      if(newJdr.start.isAfter(j.start) && newJdr.end.isBefore(j.end)){
        overlap = true;
      }
    }
    if(!overlap) {
      //it did not overlap anywhere, so it's a new entry in the list
      durations.add(newJdr);
    }
  }

  public static class JobDuration {
    LocalDateTime start;
    LocalDateTime end;

    @Override
    public String toString() {
      return "JobDuration{" +
              "start=" + start +
              ", end=" + end +
              '}';
    }

    public JobDuration(LocalDateTime pStart, LocalDateTime pEnd) {
      start = pStart;
      end = pEnd;
    }

    public LocalDateTime getStart() {
      return start;
    }

    public static JobDuration of(String sStart, String sEnd) {
      return new JobDuration(LocalDateTime.parse(sStart, FORMATTER), LocalDateTime.parse(sEnd, FORMATTER));
    }

    public Duration getDuration() {
      return Duration.between(start, end);
    }
  }
}

Running this code prints the list (with the 2 non-overlapping time frame) and the Duration of each one.

[JobDuration{start=2022-07-29T15:30:03.412754, end=2022-07-29T16:32:03.004323}, JobDuration{start=2022-07-29T16:50:03.643231, end=2022-07-29T17:35:03.234562}]
PT1H1M59.591569S
PT44M59.591331S

This means this code combines the first two entries, because they overlap. The third entry does not overlap anywhere, so it results in its own duration.

Check if time (startdate & enddate) cuts a time period

If you want to stick with long-values, I would do the following

if (!((train.getEndDate() < startdate) || (train.getStartDate() > enddate))) {...}

Alternatively, you might want to convert your long-vales to java.util.Date (new Date(long value)) so that you can use the Date-class.

There is also the very nice Joda time 2.2 API which has an Interval-class that provides the following function

overlap(ReadableInterval interval)
      Gets the overlap between this interval and another interval.

Algorithm to detect overlapping periods

Simple check to see if two time periods overlap:

bool overlap = a.start < b.end && b.start < a.end;

or in your code:

bool overlap = tStartA < tEndB && tStartB < tEndA;

(Use <= instead of < if you change your mind about wanting to say that two periods that just touch each other overlap.)

---

Related Topics