Day 5: Cafeteria

This was a fun puzzle, easy and yet rather life like.

Note: If you’re attempting to read this as a Fediverse post, you might find it rather confusing. I recommend using a web browser to read it properly, following this link.

The challenge

Today, we were given two lists, one of possibly overlapping intervals, in the form, say, 12-35 and one of numbers, like 5, 1, 78, … and we had to determine how many numbers fit into at least one of the intervals.

The idea

Once we have the list of the intervals, grab the first number and loop over the interval and see if it fits. If so, increase the counter and proceed with the next number.

The updated challenge

In the second part, we don’t need the list of numbers, just the intervals. We want to know, how many numbers are contained in the union of the intervals.

If we have only one interval [a, b], the result would be b – a + 1.

Consider two disjoint intervals [a, b] and [c, d]. In this case, the result would be b – a + 1 + d – c + 1.

If a ≤ c and the intervals touch (b + 1 = c) or overlap (c ≤ b) the union of the two intervals would be [a, max{b,d}] and we would only need to consider this union.

Hence, we first sort the intervals by their lower bounds. We use the built in Perl function sort for that, and then if the first two intervals are disjoint, increase the counter by the first’s length and throw it away.

if they touch or overlap, we change the second one to be the union of both and discard the first.

We continue until there is only one left.