57. Insert Interval

func insert(_ intervals: [Interval], _ newInterval: Interval) -> [Interval] {
        var intervals = intervals, i = 0

        //找到第一个开始比新Interval大的点
        while i < intervals.count {
            if newInterval.start < intervals[i].start {
                break
            }
            i += 1
        }
        //判断之前的那个点是不是和新的overlap, 如果是从之前就要开始merge
        if i > 0 && isOverlapped(newInterval, intervals[i-1]) {
            i = i - 1
        }
        //把不需要的加入result
        var res = intervals[0 ..< i]

        //开始merge直到不overlap为止
        var newInterval = newInterval
        while i < intervals.count && isOverlapped(newInterval, intervals[i]) {
            newInterval = mergeOverlapped(intervals[i], newInterval)
            i += 1
        }
        res.append(newInterval)

        //加入后面的部分
        res += intervals[i ..< intervals.count]
        return Array(res)
    }

    func isOverlapped(_ i: Interval, _ j: Interval) -> Bool {
        if i.end < j.start || j.end < i.start { return false}
        return true
    }

    func mergeOverlapped(_ interval1: Interval, _ interval2: Interval) -> Interval {
        return Interval(min(interval1.start, interval2.start), max(interval1.end, interval2.end))
    }