8
$\begingroup$

Right now I stuck with a problem. It seems to be really trivial one, but still it is hard for me to find an appropriate solution. The problem is: One has two intervals and are to find the intersection of them.

For instance:

  • Intersection of [0, 3]&[2, 4] is [2, 3]
  • Intersection of [-1, 34]&[0, 4] is [0, 4]
  • Intersection of [0, 3]&[4, 4] is empty set

It is pretty clear that the problem can be solved by using tests of all possible cases, but it will take a lot of time and is very prone to mistakes. Are there any easier way to tackle the problem? If you know the solution help me, please. Will be very grateful.

$\endgroup$
  • $\begingroup$ What is wrong with my question? Why was it voted down? $\endgroup$ – ohidano Feb 23 '17 at 16:06
  • 2
    $\begingroup$ A couple things.. this appears to be a homework question, if it is you should call it out and tag it as such. The context of your problem is also unclear. It could be interpreted as purely a math problem (in which case it belongs in Math.SE, not here), or a programming exercise. $\endgroup$ – Spencer Bryngelson Feb 23 '17 at 22:58
  • $\begingroup$ In case you are searching for a name for these methods, it's called Interval Arithmetic. $\endgroup$ – André Feb 24 '17 at 19:42
16
$\begingroup$

We can define a solution to this problem in the following way. Assume the input intervals can be defined as $I_{a} = [a_s, a_e]$ and $I_{b} = [b_s, b_e]$, while the output interval is defined as $I_{o} = [o_s, o_e]$. We can find the intersection $I_{o} = I_{a} \bigcap I_{b}$ doing the following:

if ( $b_s \gt a_e$ or $a_s \gt b_e$ ) { return $\emptyset$ }

else {

$o_s = \max (a_s,b_s)$

$o_e = \min (a_e,b_e)$

return $[o_s,o_e]$

}

$\endgroup$
0
$\begingroup$

In another simple way

Given:
2 Intervals
Interval 1: (start1, end1)
Interval 2: (start2, end2)

Required:
Boolean condition to check if both intervals are intersected or not

Solution:
Following TWO conditions should be true to consider that 2 intervals are intersected:
1. end2 >= start1
2. start2 <= end1

// check 2 intervals are intersected or not
if( (end2 >= start1) && (start2 <= end1) ){
    // 2 intervals are intersected
    // ...

}else{
    // 2 intervals are NOT intersected
    // ...

}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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