*This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions 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`

.