# The easiest way to find intersection of two intervals

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.

• What is wrong with my question? Why was it voted down? – ohidano Feb 23 '17 at 16:06
• 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. – Spencer Bryngelson Feb 23 '17 at 22:58
• In case you are searching for a name for these methods, it's called Interval Arithmetic. – André Feb 24 '17 at 19:42

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]$

}

Assume we only have two input intervals.

1. Make sure the start time of the first interval < the start time of the second interval.
2. Overlap means an interval's end time is after another interval's start time
public int[] overlap(int[] i1, int[] i2) {
// Make sure the start time of first interval < the start time of second interval.
if(i1.startTime > i2.startTime) {
return overlap(i2, i1);
}

// Overlap means an interval's end time is after another interval's start time
if(i1.endTime > i2.startTime) {
return new Interval(i2.startTime, Math.min(i1.endTime, i2.endTime));
}
else {
return null;
}
}

• Time complexity: O(1)
• Space complexity: O(1)

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
// ...

}