Contains in Range Falls Mainly on the Interval Methods

So there was another problem today:

Given a collection of intervals, write a function that merges all overlapping intervals and prints them out.

For example, given [1, 3], [2, 6], [8, 10], and [7, 11], the function should print [1, 6], [7, 11]. Or given [5, 12], and [8, 10] the function should print [5, 12].

You can assume that the first element of each interval is always less or equal than the second element of the interval.

This wasn’t as difficult as the last, by a long way, but it was still interesting. I did it in Swift, but, since I’m learning Haskell, I tried to apply some of the ideas from there. The result was lovely, unnecessary recursion.

The first part of this problem is finding an efficient way to check if two ranges overlap. Here’s the function that I came up with in Swift:


func overlaps (with: ClosedInterval<T>) -> Bool {
  return self.contains(with.start) || with.contains(self.start)
}

It’s a method on the “ClosedInterval” type in Swift. You can check if a closed interval contains a value easily (.contains), so I just checked if either interval contained the start of the other. That has to mean they overlap:

ho.001Then, you need a combine function. I just took the smallest “Start”, and the largest “End” from the two intervals to combine, and made a new interval from that:


mutating func combine(with: ClosedInterval<T>) {
  self = ClosedInterval(
    min(self.start, with.start),
    max(self.end,   with.end)
  )
}

Then, how to handle the array of intervals. Well, the declaration for the function has got to look like this:


func merge<T>
  (var intervals: [ClosedInterval<T>]) -> [ClosedInterval<T>]

And, since we’re being recursive, let’s get our base case:


if intervals.isEmpty {return []}

Now, for how it actually works. I popped an element off the end of the list:


var last = intervals.removeLast()

And then the function would try and merge it with everything in the list. Anything left (anything that didn’t merge) was passed recursively to the merge function again, and the single interval, formed as a result of the merging, was added on to all of that. Here it is in all of its glory:


func merge<T>
  (var intervals: [ClosedInterval<T>]) -> [ClosedInterval<T>] {
  
  if intervals.isEmpty {return []}
  
  var last = intervals.removeLast()
  
  return merge(
    intervals.reduce([ClosedInterval<T>]()) {
      
      accu, element in
      
      if last.overlaps(element) {
        last.combine(element)
        return accu
      } else {
        return accu + [element]
      }
    
    }
  ) + [last]
  
}

And some results:


let toMerge =  [
  ClosedInterval(10, 13),
  ClosedInterval(1, 3),
  ClosedInterval(2, 6),
  ClosedInterval(8, 10),
  ClosedInterval(7, 11),
  ClosedInterval(17, 21),
  ClosedInterval(23, 28),
  ClosedInterval(26, 30)
]

merge(toMerge)

// ["1...6", "7...13", "17...21", "23...30"]

Update:

But wait! There’s more. My recursion wasn’t just slow and unnecessary, it was wrong. Hmm. I’ve done a different method for the moment:

func merge<T>
  (var intervals: [ClosedInterval<T>]) -> [ClosedInterval<T>] {

  return intervals
    .sorted{$0.0.start < $0.1.start}
    .reduce([ClosedInterval<T>]()) {
      
      accu, element in
      
      if let last = accu.last where last.overlaps(element) {
        return dropLast(accu) + [last.combine(element)]
      } else {
        return accu + [element]
      }
  }
  
}

AND YET MORE:

After yet more Haskell, and yet more understanding of optionals my optional chaining is a little bit more mature these days. Check it out:

func merge<T>
  (var intervals: [ClosedInterval<T>]) -> [ClosedInterval<T>] {
    
    return intervals
      .sorted{$0.0.start < $0.1.start}
      .reduce([ClosedInterval<T>]()) {
        
        accu, element in
        
        return accu.last?.overlaps(element) ?? false ?
          dropLast(accu) + [accu.last!.combine(element)] :
          accu + [element]

    }
    
}

Or, if we add a third method to ClosedRange:

func tryCombine(with: ClosedInterval<T>) -> ClosedInterval<T>? {
  return self.overlaps(with) ? self.combine(with) : nil
}

It can become very terse. Very terse indeed:

func merge<T>
  (var intervals: [ClosedInterval<T>]) -> [ClosedInterval<T>] {
    
    return intervals
      .sorted{$0.0.start < $0.1.start}
      .reduce([ClosedInterval<T>]()) {
        
        accu, element in
        
        accu.last?.tryCombine(element).map{dropLast(accu) + [$0]} ?? accu + [element]

    }
    
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s