Jared Martin

This is my entry for

The Weekly Challenge, week 127

Task 1, "Disjoint Sets" was basically something I've done before somewhere else. In fact, what I'm using is overkill for just determining if two sets intersect. I imagine most people would probably use the FAQ answer. However, I'm a fan of what cardinal LanX of Perl Monks fame was trying to do in making set intersection a more "organic" operation. I don't know how much those ideas developed, however, so I'll be looking at the other solutions to see if there's anything new.

I actually did use my perlmonks code on real problem a few years ago, in modified form. It does the trick pretty quickly compared to other approaches. Thanks perl hashing!

You can find my code for Task #1 here.

Task 2, "Conflict Intervals" could have been turned into a repeat of Task 1 if you replaced all the integer intervals with the subset of integers they represented. (So, for example, interval (3, 7) would become subset (3, 4, 5, 6, 7).) But this time I am sure I went with the thundering herd and just did boundary checking on ranges against each other. As a nod to efficiency, I used first instead of grep at one point, but by the time you really need to use first instead of grep, you probably should consider the other big efficiency concern: Every interval is being compared to each interval that was in the list before it.

Conceivably, if you have hundreds or thousands of intervals and if you know that intersections will be high, you might gain some advantage by replacing intervals that intersect with their union. So, for example, if you have (1,3) and (2, 5) as intervals, you can replace them with the equivalent interval, (1,5). Then as you go through the rest of the list you don't have to check as many cases.

But the examples are small and there is no test data set to run against, so it's probably best to exercise the old noodle with a little problem and not soak up too much of your free time with making it a bigger problem. Or so I say ;-)

You can find my code for Task #2 here