# 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? – some1 here 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]$

}

• The notation here is extremely helpful. And the solution is so simple and clear. – cumin Apr 21 at 1:28

ahmednabil88's answer is correct. Let me give you an explanation based on simple Boolean algebra. For self-containnedness we restate the problem here:

Given two close intervals [start1, end1], [start2, end2], we want a minimal boolean expression that is true iff. the two intervals overlap.

It's hard to enuermate all the case of intersection. But there are only 2 cases when the two intervals don't overlap. The boolean expression for non-overlapping is:

$$(start1 \leq end1 < start2 \leq end2) \vee (start2 \leq end2 < start1 \leq end1)$$

We simply take the negation to get the expression for overlapping:

$$\neg \big((start1 \leq end1 < start2 \leq end2) \vee (start2 \leq end2 < start1 \leq end1)\big)$$

However, the implementation would be more efficient if we simplify the expression manually. We rewrite the expression first:

$$\neg \big((start1 \leq end1 \wedge end1 < start2 \wedge start2 \leq end2) \vee (start2 \leq end2 \wedge end2 < start1 \wedge start1 \leq end1)\big)$$

Note that $$start1 \leq end1$$ and $$start2 \leq end2$$ can be killed because they are already assumed to be true. So we have:

$$\neg \big((end1 < start2) \vee (end2 < start1)\big)$$

by De Morgan's rule, we have:

$$\neg(end1 < start2) \wedge \neg(end2 < start1)$$

by De Morgan's rule again, we conclude that:

$$end1 \geq start2 \wedge end2 \geq start1$$

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

}