PWC 050 › Merge Intervals

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.