Hacker News Reader

Comment by bumbledraven | Hacker News Reader

> given the starting and ending times of two calendar appointments, determine whether or not they conflict.

Say the first appointment goes from a to b and the second goes from c to d. What does it look like if the appointments _don't_ conflict? This happens just when one appointment ends no later than the other begins; in other words, when b ≤ c or d ≤ a. So, the appointments conflict just when not(b ≤ c or d ≤ a). We can then distribute the negation using [De Morgan's laws](https://en.wikipedia.org/wiki/Negation#Distributivity) to arrive at this: the appointments conflict just when b > c and a > d.

View on HN

If you were writing code, I would argue against using De Morgan's laws just because you can.

You're saving a few characters to make the code less obvious. Please correct me if there's some other benefit.

Usually after a mathematical simplification like this, you can find a direct explanation for it. In this case you can reason:

If two appointments conflict, that means that there is a time when they are both active. Thus each of their end times are after both of their start times. Of course, each appointment ends after it started, so that just leaves that each appointment ends after the other started. So if the appointments are a to b and c to d, then they conflict iff b > c and d > a.

(I've corrected bumbledraven's mistake of a > d vs. d > a.)

I would say, if the transformation makes the code and the reasoning behind it simpler then do it. Otherwise, know that any decent optimizing compiler can do this trick by itself so what you write only influences readability.

You have a mistake in the last not of your formula. The opposite of d<=a is d>a, not a>d.

This mistake could be made more "eyesoreous" and possibly avoided by naming the begin/end times b1, b2, e1, e2 instead of opaque letters. I would fire the OP for that alone :p

If one appointment is wholly contained in the other, then b > c and a < d.

do you mean "b > c and d > a"?

Consider appointments from 1-3 and 2-4:

a = 1, b = 3, c = 2, d = 4.

Do they conflict?

It's difficult to tell if GP miswrote, or you misunderstood, but it doesn't sound like they've made the mistake you're alluding to (I would expect them to be explicitly wrong).

Hmm.. Perhaps I did misunderstand something. But if the test for a conflict is:

b > c and a > d

with conflicting appointments from 1-3 and 2-4:

a = 1, b = 3, c = 2, d = 4

won't that evaluate to:

3 > 2 and 1 > 4

true and false

false (no conflict)

I could be wrong, but I think you have to do all four comparisons as in aldarn's comment:

https://news.ycombinator.com/item?id=14641043

(no fair peeking!)

Yes, I do not think "and" here was meant as a logical constraint.

The test is the opposite of (X ends before Y starts) and (Y ends before X starts). You only need two comparisons.

With two events, X going from xb to xe, and Y going from yb to ye, you have these possible sequences:

    xb xe yb ye (no conflict)
    xb yb xe ye (conflict)
    xb yb ye xe (conflict)
    yb ye xb xe (no conflict)
    yb xb ye xe (conflict)
    yb xb xe ye (conflict)

As long as (xb >= ye or yb >= xe) there's no conflict. You can flip those: (xb < ye and yb < xe) to get the conflict condition.

We can evaluate this expression over those cases:

    xb xe yb ye : yb < xe => false => no conflict
    xb yb xe ye : xb < ye and yb < xe => true, conflict
    xb yb ye xe : xb < ye and yb < xe => true, conflict
    yb ye xb xe : xb < ye => false => no conflict
    yb xb ye xe : xb < ye and yb < xe => true, conflict
    yb xb xe ye : xb < ye and yb < xe => true, conflict

So you only need two comparisons, and an and operation.

Yeah, you have it right. I had a nagging feeling that two comparisons ought to be enough, and something was just reversed in bumbledraven's formula. My first thought was that the 'and' should have been an 'or', but that was wrong. It was the comparisons that were reversed, as you demonstrate.

Just to compare with the previous comments, if we put your notation back into the a-b c-d format, then it would be:

conflict = c < b and a < d

It's interesting to note how the choice of names makes such a difference. With the arbitrary names a, b, c, d for the four times, it's harder to think about whether the expression is right. Which was 'c' again?

Your names xb, xe, yb, ye are still terse, but once you know that x means one appointment and y means the other, and be and e mean beginning and end, it makes it much easier to think about it.

Just make sure your data is correct, and a single comparison works: https://gist.github.com/anonymous/c02d74eb75a51dce8dcbc027a3...

Your code has two comparisons; one to figure out which one starts first, and another to figure out whether the first one ends before the second one starts. This isn't getting your data correct; knowing which one comes first isn't part of the problem description :)

It appears what they're alluding to is this part: > the appointments conflict just when b > c and a > d.

which I first understood to be a conversational statement rather than a statement of logic (which I assume GP is referring to), in which case it should be (b > c or a > d).

Reply on news.ycombinator.com