Merging Overlapping Intervals (`Range<Int>`s) in Swift

MergingOverlappingIntervals.swift

//: [Merging Overlapping Intervals](https://www.shiftedup.com/2015/05/17/programming-challenge-merging-overlapping-intervals)
//: Xcode 7.0, Swift 2.0

/*: 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.
*/

//: Note: The challenge suggests that each interval is an `Array<Int>` where `interval.count == 2` and `interval[0] <= interval[1]`. In Swift, these intervals should be modeled by the `Range<Int>` type. I am altering the challenge to suit the language, I know. [TKO]

func combinedIntervals(intervals: [Range<Int>]) -> [Range<Int>] {
 
    var combined = [Range<Int>]()
    var accumulator = (0...0) // empty range
    
    for interval in (intervals.sort{ $0.startIndex < $1.startIndex }) {
        
        if accumulator == (0...0) {
            accumulator = Range(interval)
        }
        
        if accumulator.endIndex >= interval.endIndex {
            // interval is already inside accumulator
        }
        
        else if accumulator.endIndex > interval.startIndex {
            // interval hangs off the back end of accumulator
            accumulator.endIndex = interval.endIndex
        }
        
        else if accumulator.endIndex <= interval.startIndex {
            // interval does not overlap
            combined.append(accumulator)
            accumulator = interval
        }
    }
    
    if accumulator != (0...0) {
        combined.append(accumulator)
    }
    
    return combined
}

let test1 = [(1...3), (2...6), (8...10), (7...11)]
assert(combinedIntervals(test1) == [(1...6), (7...11)])

let test2 = [(5...12), (8...10)]
assert(combinedIntervals(test2) == [(5...12)])

Thanks a lot for sharing this algorithm. I have re written it in Swift 3:

func combinedIntervals(intervals: [CountableClosedRange<Int>]) -> [CountableClosedRange<Int>] {
    
    var combined = [CountableClosedRange<Int>]()
    var accumulator = (0...0) // empty range
    
    for interval in intervals.sorted(by: { $0.lowerBound  < $1.lowerBound  } ) {
        
        if accumulator == (0...0) {
            accumulator = interval
        }
        
        if accumulator.upperBound >= interval.upperBound {
            // interval is already inside accumulator
        }
            
        else if accumulator.upperBound >= interval.lowerBound  {
            // interval hangs off the back end of accumulator
            accumulator = (accumulator.lowerBound...interval.upperBound)
        }
            
        else if accumulator.upperBound <= interval.lowerBound  {
            // interval does not overlap
            combined.append(accumulator)
            accumulator = interval
        }
    }
    
    if accumulator != (0...0) {
        combined.append(accumulator)
    }
    
    return combined
}

test case fails: [[1,4], [0,4]]

test case fails: [[1,4], [0,4]]

Intervals are sorted by lowerBound (ascending), so [0,4] would never follow [1,4]

intervals.sorted(by: { $0.lowerBound  < $1.lowerBound  } )