10
$\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
23
$\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]$

}

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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)
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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 $

| cite | improve this answer | |
$\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
    // ...

}
| cite | improve this answer | |
$\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.