# ETOOBUSY đźš€ minimal blogging for the impatient

# PWC127 - Conflict Intervals

**TL;DR**

On with TASK #2 from The Weekly Challenge #127. Enjoy!

# The 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.

Example`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.`

# The questions

Wellâ€¦ this challenge seems to go all by induction from the examples. Which meansâ€¦ letâ€™s guess a rule, and stick to that.

In this case, Iâ€™ll assume that two *conflicting* intervals share a
sub-interval or an endpoint. Hence, `(1,4)`

and `(3,5)`

conflict because
they share the sub-interval `(3,4)`

. By this definition, anyway, also
`(1,3)`

and `(3,5)`

conflict, because they share one endpoint.

Iâ€™ll also assume that itâ€™s OK to print conflicting intervals as we like it and not necessarily in the order they appear in the input sequence of intervals. This is because itâ€™s not written andâ€¦ my algorithm does not necessarily preserve the input order đź™„

# The solution

Although the challenge talks about â€ślooking backwardsâ€ť for conflicting
predecessors, I opted for a *look-ahead* approach where I take the
interval at the beginning and see if it generates any conflict ahead.

The first interval is always safe, because it has no conflicting predecessors. For each successor that the first interval conflicts with, we eliminate that interval from the list of candidates (because we know it has a conflict) and merge it with the initial one, going on to find out additional conflicting intervals up to the end.

At the end of one such pass, the first element can be safely ignored, all conflicting intervals associated to that element and other conflicting with it have been eliminated from the input list, and we can restart the process with the intervals weâ€™re left with. When we exhaust this listâ€¦ weâ€™re done.

To be fair, I started with Perl:

```
sub conflict_intervals (@intervals) {
my @conflicting; # keep the answer
while (@intervals) {
# if there is a "first" one, it's safe because it has not been
# eliminated by its predecessors. Its endpoints will be used to
# possibly eliminate successors, we keep them in two convenience
# variables.
my ($X, $Y) = shift(@intervals)->@*;
# we filter the remaining intervals ditching all those that
# conflict with ($X, $Y) or whatever it becomes on the way. In
# particular, at every conflict we expand ($X, $Y) to also
# include the conflicting item, because we will ditch it from
# the candidate "clean" intervals and put it in @conflicting.
@intervals = grep {
my ($A, $B) = $_->@*;
# this is a general check to see if the two intervals are
# disjoint. It assumes that touching intervals are conflicting.
($A - $Y) * ($B - $X) > 0 or do {
push @conflicting, $_;
$X = $A if $X > $A; # "eat" the ($A, $B) interval in ($X, $Y)
$Y = $B if $Y < $B;
0; # this interval conflicted and does not get passed along
}
} @intervals;
}
return @conflicting;
}
```

The Raku translation required very little changes, admittedly:

```
sub conflict-intervals (@intervals) {
return gather {
while @intervals {
# if there is a "first" one, it's safe because it has not been
# eliminated by its predecessors. Its endpoints will be used to
# possibly eliminate successors, we keep them in two convenience
# variables.
my ($X, $Y) = @intervals.shift.Slip;
# we filter the remaining intervals ditching all those that
# conflict with ($X, $Y) or whatever it becomes on the way. In
# particular, at every conflict we expand ($X, $Y) to also
# include the conflicting item, because we will ditch it from
# the candidate "clean" intervals and put it in @conflicting.
@intervals = @intervals.grep: -> $interval {
my ($A, $B) = |$interval;
# this is a general check to see if the two intervals are
# disjoint. It assumes that touching intervals are conflicting.
($A - $Y) * ($B - $X) > 0 or do {
take $interval;
$X = $A if $X > $A; # "eat" ($A, $B) in ($X, $Y)
$Y = $B if $Y < $B;
0; # this interval conflicted and does not get passed along
}
}
}
}
}
```

Iâ€™m stubborn as a mule and I insist on using `gather/take`

despite
the performance tax. I stand by it, though: itâ€™s such a useful construct
that Iâ€™ll not be hindered by its slowness. Until I can, anyway.
Besidesâ€¦ it might become fast one day, who knows?

I hope you found this interesting! Stay safe andâ€¦ have `-Ofun`

!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*