[Swift]LeetCode56. 合并区间 | Merge Intervals
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（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
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * public var start: Int
5 * public var end: Int
6 * public init(_ start: Int, _ end: Int) {
7 * self.start = start
8 * self.end = end
9 * }
10 * }
11 */
12 class Solution {
13 func merge(_ intervals: [Interval]) -> [Interval] {
14 guard !intervals.isEmpty else {
15 return []
16 }
17
18 var intervals = intervals
19 var index = 1
20 while index < intervals.count {
21 let interval = intervals[index]
22 var left = 0
23 var right = index
24 while left < right {
25 let leftInterval = intervals[left]
26 if interval.end < leftInterval.start || interval.start > leftInterval.end {
27 left += 1
28 continue
29 }
30
31 interval.start = min(leftInterval.start, interval.start)
32 interval.end = max(leftInterval.end, interval.end)
33 intervals.remove(at: left)
34 right -= 1
35 index -= 1
36 }
37
38 index += 1
39 }
40 return intervals
41 }
42 }100ms
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * public var start: Int
5 * public var end: Int
6 * public init(_ start: Int, _ end: Int) {
7 * self.start = start
8 * self.end = end
9 * }
10 * }
11 */
12 class Solution {
13 func merge(_ intervals: [Interval]) -> [Interval] {
14 let count = intervals.count
15 guard count > 0 else {
16 return [Interval]()
17 }
18
19 var intervals = intervals.sorted { (intervalL, intervalR) -> Bool in
20 intervalL.start < intervalR.start
21 }
22
23 var left = intervals[0].start
24 var right = intervals[0].end
25 var result = [Interval]()
26 for i in 1..<count {
27 if intervals[i].start <= right {
28 right = max(right, intervals[i].end)
29 } else {
30 result.append(Interval.init(left, right))
31 left = intervals[i].start
32 right = intervals[i].end
33 }
34 }
35 result.append(Interval.init(left, right))
36 return result
37 }
38 }104ms
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * public var start: Int
5 * public var end: Int
6 * public init(_ start: Int, _ end: Int) {
7 * self.start = start
8 * self.end = end
9 * }
10 * }
11 */
12 class Solution {
13 func merge(_ intervals: [Interval]) -> [Interval] {
14 if intervals.count < 2 {
15 return intervals
16 }
17 //排序
18 let newIner = intervals.sorted { (inter1, inter2) -> Bool in
19 return inter1.start < inter2.start
20 }
21
22 var results = [Interval]()//结果
23 results.append(newIner[0])
24 for (i,inter) in newIner.enumerated() {
25 if i == 0 {
26 continue
27 }
28 let result = results.last!
29 if inter.start <= result.end {//有重叠
30 result.end = max(result.end, inter.end)
31 } else {
32 results.append(inter)
33 }
34 }
35 return results
36 }
37 }112ms
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * public var start: Int
5 * public var end: Int
6 * public init(_ start: Int, _ end: Int) {
7 * self.start = start
8 * self.end = end
9 * }
10 * }
11 */
12 class Solution {
13 func merge(_ intervals: [Interval]) -> [Interval] {
14 var ivs = intervals
15
16 if ivs.count <= 1 {
17 return ivs
18 }
19
20 ivs.sort { $0.start < $1.start }
21
22 var res = [Interval]()
23
24 for interval in ivs {
25 if res.isEmpty || (interval.start > res.last!.end) {
26
27 res.append(interval)
28
29 } else {
30 res.last!.end = max(res.last!.end, interval.end)
31 }
32 }
33
34 return res
35 }
36 }136ms
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * public var start: Int
5 * public var end: Int
6 * public init(_ start: Int, _ end: Int) {
7 * self.start = start
8 * self.end = end
9 * }
10 * }
11 */
12 class Solution {
13 func merge(_ intervals: [Interval]) -> [Interval] {
14 guard intervals.count > 1 else{
15 return intervals
16 }
17 var intervals = intervals.sorted { (a:Interval, b:Interval) -> Bool in
18 return a.start < b.start
19 }
20 var res = [Interval]()
21 res.append(intervals.first!)
22 for i in 1..<intervals.count {
23 let last = res.last!
24 let now = intervals[i]
25 if now.start <= last.end {
26 let end = now.end >= last.end ? now.end : last.end
27 last.end = end;
28 }else{
29 res.append(now)
30 }
31 }
32
33 return res
34 }
35 }152ms
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * public var start: Int
5 * public var end: Int
6 * public init(_ start: Int, _ end: Int) {
7 * self.start = start
8 * self.end = end
9 * }
10 * }
11 */
12 class Solution {
13 func merge(_ intervals: [Interval]) -> [Interval] {
14 guard intervals.count > 1 else {
15 return intervals
16 }
17
18 let intervals = intervals.sorted(by: {$0.start < $1.start})
19
20 var res: [Interval] = []
21 var start = intervals[0].start
22 var end = intervals[0].end
23 for i in 1..<intervals.count {
24 let last = intervals[i-1]
25 let current = intervals[i]
26 end = max(last.end, end)
27 if current.start > end {
28 res.append(Interval(start, end))
29 start = current.start
30 end = current.end
31 }
32 }
33
34 end = max(intervals.last!.end, end)
35
36 res.append(Interval(start, end))
37
38 return res
39 }
40 }