calculating overlap of modular ranges So, this might be a really simple problem but I can't seem to find a nice algorithm to solve it:


  Given two ranges, [a1, a2], [b1, b2]  (all real numbers) and a real number n, find the length of the overlapping segment between the two ranges over a modulo of n.


For example, consider a 24-hour clock and the range [20, 4] (night time); for a given range, calculate the number of hours within that range that are night hours:

[13, 21] ==> 1 #[20,21]

[0, 6] ==> 4 #[0, 4]

[11, 19] ==> 0

I tried to think of it in terms of predefined segments
[a1,b1], [b2, a2] and do some math with them but it didn't work.
Maybe I should sort them somehow?

I will appreciate any help or direction, thanks!
Here is how I understand your problem. We have a modulus $n$. A generalized interval $[\![a,b]\!]$ consists of $[a,b]$ if $a &lt; b$, and of $[a,n) \cup [0,b]$ if $a &gt; b$ (assume for simplicity that $a != b$). You want to know the size of the intersection of two generalized intervals $[\![a_1,b_1]\!],[\![a_2,b_2]\!]$.

One way to solve this is to decompose each generalized interval into a disjoint union of one or two intervals, and then compute the size of the pairwise intersections (which I will let you work out yourself), and sum them up.