1457. One Pair of Intervals, Read Two Ways

Two intervals are given on one line as a b c d, with a < b and c < d. The same two pairs of numbers describe different things depending on the convention, and this problem asks for both readings of the same input.

Print three lines:

line 1 yes or no: do [a, b] and [c, d] share at least one point? line 2 yes or no: do [a, b) and [c, d) share at least one point? line 3 the LENGTH of the part they share, which is 0 when they share nothing and 0 when they share exactly one point

1 5 3 8 -> yes / yes / 2 they overlap on [3, 5] 1 3 3 5 -> yes / no / 0 they meet only at the point 3 1 2 5 6 -> no / no / 0 they are nowhere near each other

The middle line is the whole problem. [1,3] and [3,5] merely TOUCH at the point 3, and both contain it, so under the CLOSED reading they overlap. [1,3) stops just short of 3 and [3,5) starts there, so under the HALF-OPEN reading they do not. Both answers are correct, for different questions, and every interval problem you will ever meet has to say which one it means.

## What most people try first

Enumerating the points. With coordinates to 10^9 there can be 2 * 10^9 of them, and worse, the intervals are stretches of the LINE and not lists of whole numbers, so enumeration answers a third question again.

The second reflex is a cascade of cases: one before the other, one inside the other, partially overlapping on the left, partially on the right, identical. There are more of those than people expect, and the usual outcome is five branches, four of which are right.

## Two numbers settle all three questions

lo = max(a, c) the later of the two starts hi = min(b, d) the earlier of the two ends closed overlap when lo <= hi half-open overlap when lo < hi shared length = max(0, hi - lo)

Constant time, no branches beyond those three comparisons.

## Why lo and hi are the shared part

A point x lies in both closed intervals exactly when a <= x and c <= x and x <= b and x <= d. The first two together say x >= max(a, c), and the last two say x <= min(b, d). So the set of shared points is precisely the interval from lo to hi, which is non-empty exactly when lo <= hi.

Repeat the argument with the right-hand ends strict and it says the shared part of the half-open intervals is [lo, hi), which is non-empty exactly when lo < hi. The two conventions differ in exactly one character, and that is the lesson.

The length of a stretch from lo to hi is hi - lo under BOTH readings, because a single endpoint adds no length. So line 3 needs no separate case.

## The boundary that breaks a careless implementation

hi - lo and never hi - lo + 1. The + 1 counts whole POSITIONS, which is the right formula for a different problem, problem 1441, and it reports 1 for a pair sharing a single point.

And max(0, hi - lo): when the intervals miss each other entirely, hi - lo is negative, and printing it gives a negative length.

## Overflow

hi - lo is at most 2 * 10^9 when one interval spans the whole range, and a signed 32 bit integer holds 2147483647, so that FITS. The subtraction of two coordinates of magnitude 10^9 also stays inside the range. Nothing here overflows, which is worth knowing precisely rather than widening by reflex.

## Related

Every other problem in this block states its convention once and then relies on it. This one makes the convention the question. Problem 1459 asks the same double question about a whole schedule: the largest number running at once under each reading. Problem 1458 counts the pairs on which the two readings disagree.

Constraints - `-10^9 ≤ a < b ≤ 10^9` - `-10^9 ≤ c < d ≤ 10^9` - the closed reading is `[a, b]`, including both endpoints - the half-open reading is `[a, b)`, including `a` and excluding `b`