Perl Weekly Challenge 92, Part 2

Insert Interval

Part two of this weeks challenge reads

You are given a set of sorted non-overlapping intervals and a new interval. ($N)

Write a script to merge the new interval to the given set of intervals.

Algorithm Overview

This one is pretty easy. We can partition the set of intervals into three non-overlapping subsets: intervals which are completely to the left of $N (set A); intervals which intersect $N (set B); and intervals which are completely to the right of $N (set C). Any of the three subsets can be empty, but their union equals the given set of intervals.

Note that two intersection intervals include intervals where one intervals completely covers the other interval.

For the above sets, A and C are left unmodified. Set B and $N will be merged to one new interval:

  • If set B is non-empty, and the start point of the left most interval is to the left of the start point of $N, then this start point is the start point of the new interval; otherwise, the start point of $N is the start point of the new interval.
  • If set B is non-empty, and the end point of the right most interval is to the right of the end point of $N, then this end point is the end point of the new interval; otherwise, the end point of $N is the end point of the new interval.

Since the set of intervals is sorted, we can determine the new set in \mathcal{O} (N) time, if N is the number of intervals.

Solution

Perl

while (<>) {
    chomp;
    my @numbers = /[0-9]+/g;
    my @intervals;
    push @intervals => [splice @numbers => 0, 2] while @numbers;
    my $N = pop @intervals;

This reads a line of input, extracts the numbers, pairs them into intervals, and pops up the last one to play the role of $N.

    my @pre  = grep {$$_ [1] <  $$N [0]} @intervals;
    my @mid  = grep {$$_ [0] <= $$N [1] &&
                     $$_ [1] >= $$N [0]} @intervals;
    my @post = grep {$$_ [0] >  $$N [1]} @intervals;

Here we partition the set of intervals in intervals to the left of $N (@pre), intervals which intersect $N (@mid) and intervals which are to the right of $N (@post).

    my $mid  = [@mid && $mid  [0] [0] < $$N [0] ? $mid  [0] [0] : $$N [0],
                @mid && $mid [-1] [1] > $$N [1] ? $mid [-1] [1] : $$N [1]];

Create the new, merged, interval, as explained above.

    say join ", " => map {"(" . $$_ [0] . ", " . $$_ [1] . ")"}
                    @pre, $mid, @post;
}

And print the results.

Full program on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s