Perl Weekly Challenge 127: Conflict Intervals

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

Input: @Intervals = [ (3,4), (5,7), (6,9), (10, 12), (13,15) ]
Output: [ (6,9) ]

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

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.

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\).

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.