开放原子开发者工作坊

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9917865.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

---

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

---

84ms

/**
 * Definition for an interval.
 * public class Interval {
 *   public var start: Int
 *   public var end: Int
 *   public init(_ start: Int, _ end: Int) {
 *     self.start = start
 *     self.end = end
 *   }
 * }
 */
class Solution {
    func merge(_ intervals: [Interval]) -> [Interval] {
        guard !intervals.isEmpty else {
            return []
        }

        var intervals = intervals
        var index = 1
        while index < intervals.count {
            let interval = intervals[index]
            var left = 0
            var right = index
            while left < right {
                let leftInterval = intervals[left]
                if interval.end < leftInterval.start || interval.start > leftInterval.end {
                    left += 1
                    continue
                }

                interval.start = min(leftInterval.start, interval.start)
                interval.end = max(leftInterval.end, interval.end)
                intervals.remove(at: left)
                right -= 1
                index -= 1
            }

            index += 1
        }
        return intervals
    }
}

---

100ms

/**
 * Definition for an interval.
 * public class Interval {
 *   public var start: Int
 *   public var end: Int
 *   public init(_ start: Int, _ end: Int) {
 *     self.start = start
 *     self.end = end
 *   }
 * }
 */
class Solution {
    func merge(_ intervals: [Interval]) -> [Interval] {
        let count = intervals.count
        guard count > 0 else {
            return [Interval]()
        }
        
        var intervals = intervals.sorted { (intervalL, intervalR) -> Bool in
            intervalL.start < intervalR.start
        }
        
        var left = intervals[0].start
        var right = intervals[0].end
        var result = [Interval]()
        for i in 1..<count {
            if intervals[i].start <= right {
                right = max(right, intervals[i].end)
            } else {
                result.append(Interval.init(left, right))
                left = intervals[i].start
                right = intervals[i].end
            }
        }
        result.append(Interval.init(left, right))
        return result
    }
}

---

104ms

/**
 * Definition for an interval.
 * public class Interval {
 *   public var start: Int
 *   public var end: Int
 *   public init(_ start: Int, _ end: Int) {
 *     self.start = start
 *     self.end = end
 *   }
 * }
 */
class Solution {
    func merge(_ intervals: [Interval]) -> [Interval] {
                if intervals.count < 2 {
            return intervals
        }
        //排序
        let newIner = intervals.sorted { (inter1, inter2) -> Bool in
            return inter1.start < inter2.start
        }
        
        var results = [Interval]()//结果
        results.append(newIner[0])
        for (i,inter) in newIner.enumerated() {
            if i == 0 {
                continue
            }
            let result = results.last!
            if inter.start <= result.end {//有重叠
                result.end = max(result.end, inter.end)
            } else {
                results.append(inter)
            }
        }
        return results
    }
}

---

112ms

/**
 * Definition for an interval.
 * public class Interval {
 *   public var start: Int
 *   public var end: Int
 *   public init(_ start: Int, _ end: Int) {
 *     self.start = start
 *     self.end = end
 *   }
 * }
 */
class Solution {
    func merge(_ intervals: [Interval]) -> [Interval] {
        var ivs = intervals
        
        if ivs.count <= 1 {
            return ivs
        }
        
        ivs.sort { $0.start < $1.start }
        
        var res = [Interval]()

        for interval in ivs {
            if res.isEmpty || (interval.start > res.last!.end) {

                res.append(interval)

            } else {
                res.last!.end = max(res.last!.end, interval.end)
            }
        }

        return res
    }
}

---

136ms

/**
 * Definition for an interval.
 * public class Interval {
 *   public var start: Int
 *   public var end: Int
 *   public init(_ start: Int, _ end: Int) {
 *     self.start = start
 *     self.end = end
 *   }
 * }
 */
class Solution {
    func merge(_ intervals: [Interval]) -> [Interval] {
        guard intervals.count > 1 else{
            return intervals
        }
        var intervals = intervals.sorted { (a:Interval, b:Interval) -> Bool in
            return a.start < b.start
        }
        var res = [Interval]()
        res.append(intervals.first!)
        for i in 1..<intervals.count {
            let last = res.last!
            let now = intervals[i]
            if now.start <= last.end {
                let end = now.end >= last.end ? now.end : last.end
                last.end = end;
            }else{
                res.append(now)
            }
        }

       return res
    }
}

---

152ms

/**
 * Definition for an interval.
 * public class Interval {
 *   public var start: Int
 *   public var end: Int
 *   public init(_ start: Int, _ end: Int) {
 *     self.start = start
 *     self.end = end
 *   }
 * }
 */
class Solution {
    func merge(_ intervals: [Interval]) -> [Interval] {
        guard intervals.count > 1 else {
            return intervals
        }
        
        let intervals = intervals.sorted(by: {$0.start < $1.start})
        
        var res: [Interval] = []
        var start = intervals[0].start
        var end = intervals[0].end
        for i in 1..<intervals.count {
            let last = intervals[i-1]
            let current = intervals[i]
            end = max(last.end, end)
            if current.start > end {
                res.append(Interval(start, end))
                start = current.start
                end = current.end
            }
        }
        
        end = max(intervals.last!.end, end)
        
        res.append(Interval(start, end))
        
        return res
    }
}