algorithm - Given two ranges [a,b), [c,d), check if they intersect -

the google phone interview question found cscareerquestions was

given 2 ranges [a,b), [c,d), check if intersect.

http://www.reddit.com/r/cscareerquestions/comments/2xrzst/just_got_rejected_from_google_after_my_phone/

the interviewee said:

i worked out midpoints , radii of 2 ranges. checked if difference in midpoints smaller radii summed.

the interviewer mentioned 2 things. when taking difference, if 1 smaller other. said, check , make sure right way round. 10 minutes after call, realised could've used absolute value of difference instead. mentioned [) notation means inclusive, don't include last value. decremented end of each range.

what way problem? explain using examples?

here's textbook answer:

if 2 ranges don't intersect, 1 of them entirely left of other one, say: b≤c or d≤a. comparison ≤ because ranges half-open; if b=c, example, ranges don't intersect because b not in [a,b).

so ranges intersect if above not true:

not (b≤c or d≤a) ≡ not b≤c  and not d≤a ≡ b>c and d>a

---

now, real-life programming? aside above, there 1 other case 2 ranges not intersect: when 1 or both of them empty.

that's important because empty ranges tend show up, , may have arbitrary endpoints. wouldn't want report [0,2) , [1,1) intersected, because don't, , important bug.

so let's ask different question: intersection of 2 ranges? , answer pretty simple: left-hand edge of intersection greater of left-hand edges of 2 ranges, , right-hand edge lesser of right-hand edges. mathematically:

[a,b) ∩ [c,d) ≡ [ max(a,c),min(b,d) )

since half-open range empty if right-hand edge less or equal left-hand edge, can produce more resilient definition:

ranges intersect [a,b), [c,d) ≡ min(b,d) > max(a,c)