Check if time intervals overlap using integers

Question

I need to check if times A cross with times B using integers and a 24hour clock. Times that are the same don't count as crossing, but meeting.

For example: 16, 20 and 14, 18 (startA, endA and startB and endB) would return true as these times do cross, however, 14, 16 and 16, 20 meet but don't cross so they would return false. Any other combination that does not cross would return false.

Assuming that the times don't go past midnight I can just do this:

static boolean Cross(int startPeriod1, int endPeriod1, int startPeriod2, int endPeriod2) {
    return startPeriod1 < endPeriod2 && endPeriod1 > startPeriod2;
}

However, to include times that do go past midnight (e.g 16, 2 and 14, 2 which would return true) I used this solution:

static boolean timesCrossLate(int startPeriod1, int endPeriod1, int startPeriod2, int endPeriod2) {

    List<Integer> rangePeriod1;
    List<Integer> rangePeriod2;

    if (startPeriod1 > endPeriod1) {
        List<Integer> rangeStartPeriod1 = IntStream.range(startPeriod1 + 1, 25).boxed().collect(Collectors.toList());
        List<Integer> rangeEndPeriod1 = IntStream.range(0, endPeriod1).boxed().collect(Collectors.toList());
        rangePeriod1 = Stream.concat(rangeStartPeriod1.stream(), rangeEndPeriod1.stream()).collect(Collectors.toList());

    }
    else {
        rangePeriod1 = IntStream.range(startPeriod1 + 1, endPeriod1).boxed().collect(Collectors.toList());
    }

    if (startPeriod2 > endPeriod2) {
        List<Integer> rangeStartPeriod2 = IntStream.range(startPeriod2 + 1, 25).boxed().collect(Collectors.toList());
        List<Integer> rangeEndPeriod2 = IntStream.range(0, endPeriod2).boxed().collect(Collectors.toList());
        rangePeriod2 = Stream.concat(rangeStartPeriod2.stream(), rangeEndPeriod2.stream()).collect(Collectors.toList());

    }
    else {
        rangePeriod2 = IntStream.range(startPeriod2 + 1, endPeriod2).boxed().collect(Collectors.toList());
    }

    if (!Collections.disjoint(rangePeriod1, rangePeriod2)) {
        return true;
    }
    else {
        return false;
    }
}

Here I make a list of the range of times and compare the two lists to see if any elements are shared, I of course don't include the start and end numbers as that would meant that the numbers meet and not cross.

I wanted to know if there is a better/ cleaner way of doing this (apart from making the list creation part into a separate method).

Thanks :)

Answer 1

I think the comparison logic can be simplified considerably. If the last hour of a period is numerically less than the first hour, it is to be interpreted as the corresponding hour on the next day. We can add the value 24 to the last hour in that case, so that the “simple” comparison for overlapping intervals gives the correct result:

static boolean timesCrossLate(int startPeriod1, int endPeriod1, int startPeriod2, int endPeriod2) {
    if (endPeriod1 < startPeriod1) {
        endPeriod1 += 24;
    }
    if (endPeriod2 < startPeriod2) {
        endPeriod2 += 24;
    }
    return startPeriod1 < endPeriod2 && endPeriod1 > startPeriod2;
}

No lists are needed for this implementation.

A better name for the function might be periodsOverlap or something like that.

If endPeriod < startPeriod is to be interpreted as two time intervals on the same day then it is still possible to compute the result without using lists, e.g. by recursive calls of the function until the “simple” case is reached:

static boolean timesCrossLate(int startPeriod1, int endPeriod1, int startPeriod2, int endPeriod2) {
    if (endPeriod1 < startPeriod1) {
        return timesCrossLate(startPeriod1, 23, startPeriod2, endPeriod2) 
            || timesCrossLate(0, endPeriod1, startPeriod2, endPeriod2);
    } else if (endPeriod2 < startPeriod2) {
        return timesCrossLate(startPeriod1, endPeriod1, startPeriod2, 23) 
            || timesCrossLate(startPeriod1, endPeriod1, 0, endPeriod2);
    } else {
        return startPeriod1 < endPeriod2 && endPeriod1 > startPeriod2;
    }
}

Answer 2

• Missing input validation: the user could pass invalid periods, including negative numbers. One validation is to check that each argument is in the range 0-23.

• Simplification: this part:

  if (!Collections.disjoint(rangePeriod1, rangePeriod2)) {
      return true;
  }
  else {
      return false;
  }
  

  Can be simplified to:

  return !Collections.disjoint(rangePeriod1, rangePeriod2);
  

• Bug: for input [16,17], [14,17] the first function returns true, while the second function returns false. Adding Junit tests you can easily spot these issues and refactor your code safely.

• Documentation: as @Martin and @AJNeufeld have noticed in the comments, handling periods between two days can be confusing, consider documenting how to interpret periods in your context including edge cases.

• Design: as clear as the function is, it will still take a moment for the user to figure out that four integers represent two periods. A class can help to make it clearer. For example:

  class Period {
      private int start;
      private int end; 
  
      public Period(int start, int end){... /* validation */ }
  
      public boolean overlaps(Period other){...}
  
      // Getters, toString, etc.      
  } 
  

  And use it like this:

  Period p1 = new Period(16,20);
  Period p2 = new Period(14,18);
  boolean overlap = p1.overlaps(p2);
  

  The class name tells the user that it's a period and the method overlaps suggests that it's an operation between periods.

• Possible extension: representing a period with integers can be enough for your use case, but has its limitations. For example, in your model the longest period can be of two days. Why not three days or one month? Two periods of one month might overlap by one day.

  To support that, java.time would be a reasonable choice, especially the class LocalDateTime. After replacing int with LocalDateTime in the class Period, the method overlap could become:

  public boolean overaps(Period other) {
      return this.start.isBefore(other.getEnd()) && this.end.isAfter(other.getStart());
  }
  

Answer 3

Bugs

        rangePeriod1 = IntStream.range(startPeriod1 + 1, endPeriod1).boxed().collect(Collectors.toList());

Consider the period from 2 until 4. It fully encompasses 2:00-2:59 and 3:00-3:59. However, rangePeriod1 would be filled with just {3}. This is forgetting the entire starting hour.

If you compared this with 1 until 3, which will similarly populate rangePeriod2 with {1}, you will conclude they do not overlap, but we know they do.

You should not be using + 1 on the starting times. If you omitted the + 1, then 2 until 4 would produce {2, 3}, and 1 until 3 would produce {1, 2}, which have the common hour {2}.

Inconsistencies

        List<Integer> rangeStartPeriod1 = IntStream.range(startPeriod1 + 1, 25).boxed().collect(Collectors.toList());
        List<Integer> rangeEndPeriod1 = IntStream.range(0, endPeriod1).boxed().collect(Collectors.toList());
        rangePeriod1 = Stream.concat(rangeStartPeriod1.stream(), rangeEndPeriod1.stream()).collect(Collectors.toList());

If you consider the times 16 until 2, you produce rangeStartPeriod1 as {17, 18, 19, 20, 21, 22, 23, 24} and rangeEndPeriod1 as {0, 1}. You add these lists together to form rangePeriod1.

Why does the list contain both 0 and 24? The time period 24:00-24:59 should be considered to be 00:00-00:59; these should not be distinct time periods.

Answer 4

Simplification

If what you want is a shorter code, the function can be simplified to this;

static boolean overlap(int s1, int e1, int s2, int e2) {
    List<Integer> f = IntStream.range(s1, s1 > e1 ? e1 + 24 : e1).map(i -> i % 24).boxed().collect(Collectors.toList());
    List<Integer> s = IntStream.range(s2, s2 > e2 ? e2 + 24 : e2).map(i -> i % 24).boxed().collect(Collectors.toList());
    return f.stream().filter(s::contains).collect(Collectors.toSet()).size() > 0;
}

I'll add Python version, because I'm not familiar with Java and this is what I tried to write.

def overlap(s1, e1, s2, e2):
    return len({i % 24 for i in range(s1, e1 + 24 * (s1 > e1))}.intersection(
               {i % 24 for i in range(s2, e2 + 24 * (s2 > e2))})) > 0