*This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)*

Task #1 this week asks us to merge integer ranges. Here is the task description:

*Write a script to merge the given intervals where ever possible.*

[2,7], [3,9], [10,12], [15,19], [18,22]

*The script should merge [2, 7] and [3, 9] together to return [2, 9].*

*Similarly it should also merge*

**[15, 19]**and**[18, 22]**together to return**[15, 22]**.*The final result should be something like below:*

[2, 9], [10, 12], [15, 22]

Of course, we could brute force it by comparing every interval with every other interval for an O(*n*²) solution. But there is a relatively straightforward algorithm to solve this in O(*n* log *n*) time.

We first sort the intervals in order of their *smallest* value (e.g., **[2,5]** < **[3,4]** because 2 < 3. (Sorting is where the O(*n* log *n*) complexity comes from.) In Perl, we can sort like so (`@_`

contains an array of arrays (AoA), like `[2,7], [3,9], ...`

):

```
sort { $a->[0] <=> $b->[0] } @_
```

In Raku, it’s even easier:

```
@int.sort: { .head }
```

The reason we sort is apparent when we consider how to actually merge the intervals. With **[2,5], [3,4]** properly sorted, we can look at the “inside” numbers (in this case, 5, and 3). Since 5 ≥ 3, the ranges overlap and can be merged. In order to do that, we basically throw away the middle numbers and merge the outside numbers:

```
[2,5] [3,4]
[2 , 4]
[2,4]
```

The code more or less writes itself now.

## Perl

In Perl, I decided to use `reduce`

from List::Util for a bit of fun, making the code somewhat smaller and a bit more functional:

```
sub merge_int {
reduce {
(@$a and $a->[-1][1] >= $b->[0]) ?
$a->[-1] = [ $a->[-1][0], $b->[1] ] : push @$a, $b;
$a;
} [] => sort { $a->[0] <=> $b->[0] } @_;
}
```

I’m using the common trick of feeding `reduce`

an initial element (here, `[]`

), to start off the reduction, because I want an array ref when I’m done. The body of the `reduce`

block just compares the “inside” numbers of the last element in `$a`

(which is our array ref result) and `$b`

, and if `$a`

‘s last element’s last number is greater or equal to `$b`

‘s first number, then we merge those. Otherwise, we just push `$b`

into `@$a`

without modification.

## Raku

My Raku solution also uses `reduce`

:

```
sub merge-int( **@int ) {
reduce -> $res, $e {
($res.tail and $res.tail.tail ≥ $e.head) ??
($res.tail.tail = $e.tail) !! $res.push: $e;
$res
}, [], |@int.sort: { .head };
}
```

I definitely prefer the Raku code. I think the `head`

and `tail`

keywords are a nice way to avoid some of the array index fatigue I sometimes get when implementing algorithms like this. The sort code is a thing of beauty, thanks to Raku’s support for sorting based off of a single element, like `.head`

.