15
\$\begingroup\$

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:

enter image description here

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);
        }
    }
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is that Interval constructor really private? How then are you creating new instances of it? Please show your real actual code. \$\endgroup\$ – Simon Forsberg Nov 1 '18 at 13:32
  • \$\begingroup\$ @SimonForsberg Yes, it is. The Interval class and the isThereOverlap method, both reside in the same class. \$\endgroup\$ – Eugene S Nov 1 '18 at 13:40
6
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ Thank you very much for your elaborate answer. Did you come up with this simplified expression from mere observation or is there some known approach to problems like this? Thanks again. \$\endgroup\$ – Eugene S Nov 1 '18 at 13:12
  • \$\begingroup\$ @Eugene, it's a problem I've seen before in slightly different form (and different programming language). I do find that these interval primitives confuse my brain when I'm writing them (but once I've implemented the primitives, then they make code much easier to work with). \$\endgroup\$ – Toby Speight Nov 1 '18 at 15:14
  • \$\begingroup\$ Good answer. @EugeneS I did a formal proof of this using Boolean algebra in about 1990 or so because my manager was sceptical. Essentially you can show that for the exhaustive set of conditions for every range overlap scenario the conditions which Toby has outlined are true, making all of the other conditions redundant. \$\endgroup\$ – Joel Brown Nov 1 '18 at 21:36
  • \$\begingroup\$ @EugeneS: This is a very well known interview question; I've seen it countless times. It is usually framed as "tell me if these two rectangles overlap", but that is just a special case of solving "tell me if these two lines overlap" for both the horizontal and the vertical sides of the rectangles. Your problem is the simpler "lines overlap" form. \$\endgroup\$ – Eric Lippert Nov 1 '18 at 22:46
  • 2
    \$\begingroup\$ @Eric, another factor that make date calculations good for interviews is the range of corner cases that you can use to stretch the strong candidates (time zones, daylight saving, leap seconds, historical calendar, etc.). \$\endgroup\$ – Toby Speight Nov 2 '18 at 8:24
8
\$\begingroup\$

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));
}
\$\endgroup\$
3
  • 7
    \$\begingroup\$ On Code Review we expect answers to review the code of the question - if your answer is an alternate solution to the same problem the OP faced, then your answer should explain the differences and why they are improvements. Unfortunately your answer does not do this. Further, the solution you provide has significant bugs - it reports some non-overlapping times as being overlapping times. \$\endgroup\$ – rolfl Nov 1 '18 at 11:37
  • 3
    \$\begingroup\$ hi @rolfl ok, but i thought it was obvious as the question asked for a more concise alternative. I've also double checked the code for issues and can't see any obvious bugs, any pointers? \$\endgroup\$ – elvaston5 Nov 1 '18 at 12:55
  • 4
    \$\begingroup\$ Argh... @elvaston5 - I hate when I am wrong. Your code does not have a bug. Regardless, we do expect code review answers to be more than just a "code drop" of an alternate solution. Your answer makes no reference back to the actual code in the OP's question, and only solves the same problem, differently (admittedly more concisely). Let me edit it a little, and try to show the difference, it may be subtle, but it is real. \$\endgroup\$ – rolfl Nov 1 '18 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.