# ETOOBUSY đźš€ minimal blogging for the impatient

# PWC092 - Insert Interval

**TL;DR**

On with TASK #2 from the Perl Weekly Challenge #092. Enjoy!

# The challenge

You are given a set of sorted non-overlapping intervals and a new interval. Write a script to merge the new interval to the given set of intervals.

# The questions

I think that the examples here help a lot *by example*. Basically the
expected output is a sequence of non-overlapping intervals, sorted in
ascending order, much like the first input.

The intervals seem to be defined by integers, but I guess that itâ€™s fair to assume whatever number that can be represented by the computer.

# The solution

I think that this challenge requires a bit of *discipline*.

```
sub insert_interval ($S, $N) {
my @S = map { [$_->@*] } $S->@*;
my ($l, $h) = $N->@*;
my @retval;
# first of all, "transfer" all preceding intervals
push @retval, shift(@S) while @S && $S[0][1] < $l;
if (! @S) { # all intervals were preceding, easy
push @retval, [$l, $h];
return \@retval;
}
# now $S[0] might be after the new interval
if ($S[0][0] > $h) {
push @retval, [$l, $h], @S;
return \@retval;
}
# now there is some overlap between $S[0] and $N. We can fix the start
$l = min($l, $S[0][0]);
# ... and look for the end...
while (@S && $h >= $S[0][0]) {
$h = max($h, $S[0][1]);
shift @S;
}
push @retval, [$l, $h], @S;
return \@retval;
}
```

The copies at the beginning is to avoid spoiling the inputs. This is a design choice, you might prefer something different.

The first loop takes care to transfer all intervals that come *completely
before* the new one to the list that we will eventually return (held in
`@retval`

). This can lead to three situations:

- the input list is completely transferred because the new interval is higher than everything already in the list: in this case, we just add the new interval and weâ€™re done. Something like this:

```
N----N
S-----S S-----S S--S
|<---- all lower --->|
```

- otherwise, there is the possibility that all the remaining items in
`@S`

are*higher*than the new interval. Easily enough, we put the new interval in place, followed by the remaining items in`@S`

, and we call it a day. As an example:

```
N----N
S-----S S-----S S--S S----S S--------S
|<---- all lower --->| |<-- all higher --->|
```

- last, there is some degree of
*overlapping*between the new interval and whatâ€™s currently at the beginning of`@S`

, so we have to go on. The following is an example, but there are a lot of cases here:

```
N------------N
S-----S S-----S S------S S--S S----S S--------S
|<- all lower ->| |<- overlap ->| |<-- all higher --->|
```

In general, we will have to insert a new range that is the merge of the new
interval and one or more intervals in `@S`

. This new range will start with
the lowest of the two lower boundaries, so we can save it immediately. The
following is an example in which the first overlapping interval in S has a
lower bound that is smaller than the lower bound of the new interval N:

```
N--...
... S-----...
| 1st overlapping
v
X start of new merged range
```

To find the upper bound we have to look in `@S`

until we find overlaps. For
whatever overlap, we keep the higher value and check the next interval,
until thereâ€™s no more overlap. At this point, we also know the upper bound
of the new *merged* interval, and we can add it to `@retval`

, followed by
whatâ€™s left in `@S`

. The following picture shows an example in which the
upper bound of the new interval is higher than the upper bound of the last
overlapping interval.

```
...-------------------------N
... S----------S | S----S S--------S
... last overlapping --^ | |<-- all higher -->|
v
... end of new merged range X
```

How to find out the first interval in S that is no more overlapping with the
new interval N? After we have found the first overlapping one, we can check
whether the upper bound of N is greater than, or equal to, the lower bound
of the interval in S. If it is, then there is an overlap; otherwise, the
interval in S is beyond N and makes part of the â€śall higherâ€ť part. This is
the sense of the condition in the last `while`

loop, where `$h`

is the
candidate upper bound for the interval to insert so far, and `$S[0][0]`

is
the lower bound of the interval we are comparing against (in the loop, we
`shift @S`

so the first item is always the one we are considering in each
round):

```
while (@S && $h >= $S[0][0]) {
$h = max($h, $S[0][1]);
shift @S;
}
```

I guess itâ€™s all for todayâ€¦ good bye and stay safe!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*