4
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What is "the length of the overlapping segment ... over a modulo of $n$"? $\endgroup$
    – Yuval Filmus
    Commented Mar 14, 2016 at 19:57
  • $\begingroup$ @YuvalFilmus in the clock example it is the total number of hours between the beginning of the range and its end.. |[23, 1]| = 2 $\endgroup$
    – user20561
    Commented Mar 14, 2016 at 21:13

1 Answer 1

Reset to default
1
$\begingroup$

Here is how I understand your problem. We have a modulus $n$. A generalized interval $[\![a,b]\!]$ consists of $[a,b]$ if $a < b$, and of $[a,n) \cup [0,b]$ if $a > 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ eventually I solved it using these assumptions and 7 if-statements, checking whether a1, a2, both or none of them are inside [b1,b2] and then calculating accordingly. Thanks :) $\endgroup$
    – user20561
    Commented Mar 14, 2016 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.