# Perl Weekly Challenge 127: Conflict Intervals

by Abigail

## Challenge

You are given a list of intervals.

Write a script to find out if the current interval conflicts with any of the previous intervals.

### Examples

Input: @Intervals = [ (1,4), (3,5), (6,8), (12, 13), (3,20) ]
Output: [ (3,5), (3,20) ]

• The 1st interval (1,4) do not have any previous intervals to compare with, so skip it.
• The 2nd interval (3,5) does conflict with previous interval (1,4).
• The 3rd interval (6,8) do not conflicts with any of the previous intervals (1,4) and (3,5), so skip it.
• The 4th interval (12,13) again do not conflicts with any of the previous intervals (1,4), (3,5) and (6,8), so skip it.
• The 5th interval (3,20) conflicts with the first interval (1,4).
Input: @Intervals = [ (3,4), (5,7), (6,9), (10, 12), (13,15) ]
Output: [ (6,9) ]

• The 1st interval (3,4) do not have any previous intervals to compare with, so skip it.
• The 2nd interval (5,7) do not conflicts with the previous interval (3,4), so skip it.
• The 3rd interval (6,9) does conflict with one of the previous intervals (5,7).
• The 4th interval (10,12) do not conflicts with any of the previous intervals (3,4), (5,7) and (6,9), so skip it.
• The 5th interval (13,15) do not conflicts with any of the previous intervals (3,4), (5,7), (6,9) and (10,12), so skip it.

## Discussion

The description of the challenge and its examples are conflicting. The description says it wants us to determine something, so, seeking a yes/no answer. However, the examples actually report some of the intersecting intervals.

Furthermore, the challenge talks about "the current interval", without specifying what a current interval is.

What we will do is to take a set of intervals (each set on its own line), and return a true value if there is at least one pair of intersecting intervals, and false otherwise.

The challenge is also silent on what kind of intervals we have. Are they one-dimensional? Multidimensional? Are the coordinates integers? Rationals? Reals? Complex numbers? To make life easier for ourselves, we assume all intervals line on the line, and have positive integer coordinates. (Since there is no description, all we have to go by is the examples, which use intervals with positive integer coordinates on the line).

### Interval Tree

Now, the most efficient way would be to build an interval tree, which can be build in $$\mathcal{O} (N \log N)$$ time, with a query time of $$\mathcal{O} (\log N)$$ (if we all want to know there is an intersection), and which can be updated in $$\mathcal{O} (\log N)$$ time.

We will however use a quadratic algorithm, checking each pair of intervals, stopping as soon as we find an intersection.

## Solution

Two intervals, $$I = (i_l, i_h)$$ and $$J = (j_l, j_h)$$, with $$i_l < i_h$$ and $$j_l < j_h$$ intersect if and only if: $$i_h \geq j_l \wedge i_l \leq j_h$$.

### Perl

Given the above statement, we start off with method which takes two intervals as parameters, and which returns true if the two intervals intersect, and false otherwise. The two intervals are given as two element arrays:

my sub intersects ($x,$y) {($$x [1] >=$$y [0]) && ($$x [0] <=$$y [1])}


We're assuming the input is on one line, $_, and contains positive integers are coordinates. We will repeatedly read two integers, and turn them into an interval: my @intervals = map {[split /[^0-9]+/]} /[1-9][0-9]*[^0-9]+[1-9][0-9]*/g;  Now we're going to make sure the first coordinates of each interval is less than the second: foreach my$interval (@intervals) {
@$interval = reverse @$interval if $$interval [1] <$$interval [0];
}


With that, we can check each pair looking for an intersection. If we have found one, we're done. Else, we continue:

for (my $i = 1;$i < @intervals; $i ++) { for (my$j = 0; $j <$i; $j ++) { if (intersects$intervals [$i],$intervals [\$j]) {
say 1;
exit;
}
}
}
say 0;


Find the full program on GitHub.

### Other languages.

We also have a solution in AWK, which works in a very similar way.