func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
    var result: [[Int]] = []
    var newInterval = newInterval
    var i = 0
    
    // Adding the precending internvals of the newInternal into the result array
    while i < intervals.count && intervals[i][1] < newInterval[0] {
        result.append(intervals[i])
        i += 1
    }
    
    // find overlapped internvals
    while i < intervals.count && intervals[i][0] <= newInterval[1] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    }
    result.append(newInterval)
    
    // Add the rest of internals
    while i < intervals.count {
        result.append(intervals[i])
        i += 1
    }
    
    return result
}

print(insert([[1,3],[6,9]], [2,5])) // [[1,5],[6,9]]
print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])) // [[1,2],[3,10],[12,16]]

func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
    if intervals.isEmpty { return [newInterval] }
    if newInterval.start > intervals.last!.end { return intervals + [newInterval] }
    if newInterval.end < intervals.first!.start { return [newInterval] + intervals }

    // binary search for first interval with end >= newInterval.start
    var left = 0, right = intervals.count-1, mid: Int        
    while left < right {
        mid = (left + right) / 2
        if intervals[mid].end >= newInterval.start { right = mid }            
        else { left = mid + 1 }
    }
    let mergeStartIndex = left

    // binary search for last interval with start <= newInterval.end
    left = 0; right = intervals.count-1
    while left < right {
        mid = (left + right + 1) / 2            
        if intervals[mid].start <= newInterval.end { left = mid }
        else { right = mid - 1 }
    }
    let mergeEndIndex = left

    if mergeEndIndex < mergeStartIndex  { // not ovelapping any intervals
        return Array(intervals[...mergeEndIndex]) + [newInterval] + Array(intervals[mergeStartIndex...])
    }

    let insertedInterval = [min(intervals[mergeStartIndex].start, newInterval.start),
                            max(intervals[mergeEndIndex].end, newInterval.end)]

    return Array(intervals[..<mergeStartIndex]) + [insertedInterval] + Array(intervals[(mergeEndIndex+1)...])
}

extension Array where Element == Int {
    var start: Int { self[0] }
    var end: Int { self[1] }
}

print(insert([[1,3],[6,9]], [2,5])) // [[1,5],[6,9]]
print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])) // [[1,2],[3,10],[12,16]]