# Insert Interval

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.