# PWC 050 › Merge Intervals

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

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-> <=> \$b-> } @_
```

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] >= \$b->) ?
\$a->[-1] = [ \$a->[-1], \$b-> ] : push @\$a, \$b;
\$a;
} [] => sort { \$a-> <=> \$b-> } @_;
}
```

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