RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved set intersections and merging intervals. (Note that this is open until 29 August 2021.)

TASK #1 › Disjoint Sets

You are given two sets with unique integers.

Write a script to figure out if they are disjoint.

I.e. they have no members in common, which is the same as saying that the intersection of the two sets is empty.

The "modern" languages on my palette have sets and set operations built in, so for example in Raku:

  my $sa=set @a;
  my $sb=set @b;
  my $inter=$sa (&) $sb;
  if $inter.elems == 0 {
    return 1;
  } else {
    return 0;
  }

Ruby has &, and Python and Rust have an intersection() method in their Set class. So that's easy.

Perl doesn't have a set class, but its hashes are ferociously optimised; so I turn the first set into a hash (the values are irrelevant, it's just the keys that matter), then test each member of the second set to see if it's in the first.

sub ds {
  my ($a,$b)=@_;
  my %h=map {$_ => 1} @{$a};
  foreach my $n (@{$b}) {
    if (exists $h{$n}) {
      return 0;
    }
  }
  return 1;
}

PostScript doesn't have sets either, but it does have dicts which include a known method, so I use the same trick. (Interesting how divergent the terminology is round associative arrays, starting with whether they're called that, a dictionary, a hash, a map, a collection or a table. For testing whether a particular key is defined, we might have exists, known, has_key?, in, contains… the idea has been around for a while, I believe first getting language support in 1969's SNOBOL4, so it's surprising the terminology hasn't settled out the way e.g. arrays and indices have.)

/ds {
    dup length dict /dd exch def
    {
       dd exch 1 put
    } forall
    /dj 1 def
    {
        dd exch known {
            /dj 0 def
            exit
        } if
    } forall
    dj
} def

TASK #2 › Conflict Intervals

You are given a list of intervals.

Write a script to find out if the current interval conflicts with any of the previous intervals.

Not quite the standard coding-interview problem (see PWC #50), which would ask you to reduce the intervals to a minimal set (e.g. if you had (1,3) and (2,4) you'd merge them and spit out (1,4)). One normally starts the approach to that problem by sorting the input, but the desired result here will differ based on the order in which things occur (the first interval given can never conflict with anything).

So for each interval after the first, check all earlier intervals for possible overlap. If we find one, put this interval in the output queue and go on to the next one. One might also do the merge to reduce the list of earlier intervals that need to be checked, but I'm not convinced it would be helpful.

Any overlap will match at least one of these conditions:

• the lower bound lies within the earlier interval
• the upper bound lies within the earlier interval
• the lower bound is below the earlier interval, and the upper bound is above it

The Ruby code is probably the easiest to read.

def ci(a)
  o=[]
  1.upto(a.length-1) do |i|
    0.upto(i-1) do |j|
      if (a[i][0] >= a[j][0] && a[i][0] <= a[j][1]) ||
         (a[i][1] >= a[j][0] && a[i][1] <= a[j][1]) ||
         (a[i][0] <= a[j][0] && a[i][1] >= a[j][1]) then
        o.push(a[i])
        break
      end
    end
  end
  return o
end

Full code on github.