Checking if two time intervals overlap

Question

I have two time intervals i1 and i2, each defined by two values, begin and end (epoch time). I need to write a function returning a boolean value indicating whether the intervals overlap.

According to my understanding, an overlap can occur in four following cases:

while the last case (where the i2 is fully included within i1 is already covered by first two cases so can be dismissed.

The remaining three cases lead me to the following logic:

private static boolean isThereOverlap(Interval t1, Interval t2) {

        return t1.begin.isAfter(t2.begin) && t1.begin.isBefore(t2.end) ||
                t1.end.isAfter(t2.begin) && t1.end.isBefore(t2.end) ||
                t1.begin.isBefore(t2.begin) && t1.end.isAfter(t2.end);
}

where:

t1 and t2 represent i1 and i2 accordingly.

I wonder whether there's a more concise way to identify the overlap or a way to simplify the code?

EDIT1:

Including the Interval class which is utilizing java.time:

import java.time.Instant;

private class Interval {
        private Instant begin;
        private Instant end;

        private Interval(long begin, long end) {
            this.begin = Instant.ofEpochMilli(begin);
            this.end = Instant.ofEpochMilli(end);
        }
    }

Answer 1

Negating the no-overlap case

You mention four separate cases where two time intervals overlap. You then reduce it to three by pointing out that one case is really the intersection of two of the other cases. So checking those cases implicitly checks the fourth. But this is more complicated than it needs to be. Instead of thinking about when they overlap, think about when they don't.

There are only two cases where the intervals do not overlap, and they are mirror images of each other. Two intervals do not overlap when one ends before the other begins. Because either one can (a priori) be the one that ends first, this requires two checks, as coded here:

private static boolean hasOverlap(Interval t1, Interval t2) {
    return !t1.end.isBefore(t2.begin) && !t1.begin.isAfter(t2.end);
}

I changed the name to hasOverlap as being simpler.

I distributed the negation over the union to get an intersection of negations. The two are logically equivalent.

This code implicitly assumes that the time intervals are closed. I.e. that they can overlap if one interval starts at the exact time that the other ends. If that is not how intervals are supposed to work, you can change it. E.g. to

    return t1.end.isAfter(t2.begin) && t1.begin.isBefore(t2.end);

This will not match if one interval starts when the other ends but will match when there is an overlapping interval (as opposed to a point of intersection).

A variant of this was already suggested in this answer.

One version is not better than the other. It really depends on your requirements. Is it a requirement that a point of intersection be considered overlap? Or should only intervals broader than a point count?

Your original is compatible with the latter definition.

Simplifying the overlap case

Another way of reaching the same conclusion is to realize that your third case is also a special version of your first case. The second interval begins after the first and before the first ends. As such, it doesn't matter whether the second interval ends before or after the first. It overlaps regardless. Same thing with the third case and the second case, only it's the end of the second interval that is within the first interval. So you can get rid of the third case.

You actually have a bug if your intention was to check for the third case and not the fourth.

            t1.begin.isBefore(t2.begin) && t1.end.isAfter(t2.end);

That's a check for the fourth case (the first interval entirely encloses the second, starting before it and ending after). You are implicitly assuming that the third case is covered by the other cases. Even though your logic says that you are supposed to be eliminating the fourth case and checking the third. You checked the fourth and eliminated the third. Of course, since both are redundant, the bug did not affect functionality.

The final observation is that you know the beginning of an interval is before the end (logically). So you don't need to compare both the beginning and the end to the same point in the other interval. If the end of one interval is before the beginning of the other, then the beginning is as well. And the symmetric relationship. This reduces from four comparisons to check the first two cases to just two. You won't know which of the overlap cases holds, but you'll know that one does.

Answer 2

The code looks well presented, and it's clear how it maps to the problem statement.

The one thing that's not well defined is how we deal with exact equality of times. I'm assuming that intervals are always half-open (i.e. including the start time, but excluding the end time); it would be wise to add suitable comments to ensure that all readers agree on what's expected.

---

It's possible to simplify considerably, because in all cases we want (and none we don't), t1 ends after t2 begins and t2 ends after t1 begins, giving us a simpler expression:

t1.begin.isBefore(t2.end) && t2.begin.isBefore(t1.end)

---

If the Interval class is under your control, consider making this method a public instance method of that class. You might also want to check that the parameters are not null, if users might use that to indicate an empty interval:

if (t1 == null || t2 == null)
    return false;

(this latter is an argument against using an instance method, as then the caller would need to check t1 isn't null).

Answer 3

Your code uses an algorithm that directly tests for an overlap of time spans, but a simpler algorithm is to check for a non-overlap - to check for whether the time-spans are completely distinct. The spans are distinct if the first span starts after the other ends, or ends before the other one starts. This test is easy. The spans overlap if they are not distinct, so you can negate the logic for the isThereOverlap method.

private static boolean isThereOverlap(Interval t1, Interval t2) {
    return !(t1.end.isBefore(t2.begin) || t1.begin.isAfter(t2.end));
}