Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: