The easiest way to find intersection of two intervals

Question

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.

Answer 1

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

}

Answer 2

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 $

Answer 3

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)

Answer 4

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

}