Hacker News Reader

Comment by tkxxx7 | Hacker News Reader

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

View on HN

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

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

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

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