Insert Interval Problem in Swift

InsertInterval.md

Insert Interval Problem in Swift

I was working on this problem and wondered how it would look in Swift.

Given an array of non-overlapping and sorted intervals, insert a new interval into the array and merge with existing intervals if necessary.

For example, given intervals:

  [(1,3), (6,9)]

Inserting (2,5) should result in:

  [(1,5), (6,9)]

Straightforward Approach

We'll use a tuple to represent intervals.

typealias Interval = (start: Int, end: Int)

func insert(new: Interval, into elements: [Interval]) -> [Interval] {
    var result: [Interval] = []
    var n = new
    for e in elements {
        if e.end < n.start {
            result.append(e)
        } else if n.end < e.start {
            result.append(n)
            n = e
        } else {
            n = (
                start: min(e.start, n.start),
                end: max(e.end, n.end)
            )
        }
    }
    result.append(n)
    return result
}

insert((2, 5), into: [(1,3), (6,9)])

Using Built-In Interval Type

Swift has a built-in type for intervals: ClosedInterval. Let's use that. ClosedInterval conforms to IntervalType but we will want to constrain our implementation to ClosedInterval because the sementics are different for other IntervalTypes like HalfOpenInterval.

func insert<C: Comparable>(new: ClosedInterval<C>, into elements: [ClosedInterval<C>]) -> [ClosedInterval<C>] {
    var result: [ClosedInterval<C>] = []
    var n = new
    for e in elements {
        if e.end < n.start {
            result.append(e)
        } else if n.end < e.start {
            result.append(n)
            n = e
        } else {
            let start = min(e.start, n.start)
            let end = max(e.end, n.end)
            n = ClosedInterval(start, end)
        }
    }
    result.append(n)
    return result
}

insert(2...5, into: [1...3, 6...9])

Alternately, we could convert tuple intervals into an array of ClosedInterval

let intervals = [(1,3), (6,9)].map(ClosedInterval.init)
insert(2...5, into: intervals)

Using Built-In Interval Type and Operator Overloading

First, let's create a convenience function for combining two intervals.

  infix operator ++ { associativity left precedence 130 }
  
  func ++ <C: Comparable>(lhs: ClosedInterval<C>, rhs: ClosedInterval<C>) -> ClosedInterval<C> {
      let start = min(lhs.start, rhs.start)
      let end = max(lhs.end, rhs.end)
      return ClosedInterval(start, end)
  }

Now we can do things like this

  1...2 ++ 3...4 // results in 1...4

Lets also define the comparison operators for the interval

func < <C: Comparable>(lhs: ClosedInterval<C>, rhs: ClosedInterval<C>) -> Bool {
    return lhs.end < rhs.start
}

func > <C: Comparable>(lhs: ClosedInterval<C>, rhs: ClosedInterval<C>) -> Bool {
    return lhs.start > rhs.end
}

Now the insert algorithm again, this time as an operator on ClosedInterval array and a new ClosedInterval.

func += <C: Comparable>(elements: [ClosedInterval<C>], new: ClosedInterval<C>) -> [ClosedInterval<C>] {
    var result: [ClosedInterval<C>] = []
    var n = new
    for e in elements {
        if e < n {
            result.append(e)
        } else if n < e {
            result.append(n)
            n = e
        } else {
            n = n ++ e
        }
    }
    result.append(n)
    return result
}

let ii = [(1,3), (6,9)].map(ClosedInterval.init)
ii += ClosedInterval(2,5)

We can do this even more tersely

ii += (2...5)

Using only literals

[1...3, 6...9] += (2...5) // Returns in [1...5, 6...9]

You may be interested in my SwiftInterval proof of concept library: A multi-interval type with arithmetic calculations and inclusive/exclusive borders: https://github.com/Kametrixom/SwiftInterval