[Swift]LeetCode986.区间列表的交集|IntervalListIntersections

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集。

（形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）

示例：

输入：A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意：输入和所需的输出都是区间对象组成的列表，而不是数组或列表。

提示：

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

240ms

 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 intervalIntersection(_ A: [Interval], _ B: [Interval]) -> [Interval] {
14         var ans = [Interval]()
15         var i = 0, j = 0
16 
17         while i < A.count && j < B.count {
18             // Let's check if A[i] intersects B[j].
19             // lo - the startpoint of the intersection
20             // hi - the endpoint of the intersection
21             let lo = max(A[i].start, B[j].start)
22             let hi = min(A[i].end, B[j].end)
23             if lo <= hi {
24                 ans.append(Interval(lo, hi))
25             }
26             // Remove the interval with the smallest endpoint
27             if A[i].end < B[j].end {
28                 i += 1
29             }
30             else {
31                 j += 1
32             }
33         }
34         return ans        
35     }
36 }

248ms

 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 intervalIntersection(_ A: [Interval], _ B: [Interval]) -> [Interval] {
14         var a = 0
15         var b = 0
16         var res = [Interval]()
17         while a < A.count && b < B.count {
18             if let interval = intersection(A[a], B[b]) {
19                 res.append(interval)
20             }
21             if A[a].end < B[b].end {
22                 a += 1
23             } else if A[a].end > B[b].end {
24                 b += 1
25             } else {
26                 a += 1
27                 b += 1
28             }
29         }
30         return res
31     }
32     
33     private func intersection(_ A: Interval, _ B: Interval) -> Interval? {
34         if B.start > A.end || A.start > B.end { return nil }
35         return Interval(max(A.start, B.start), min(A.end, B.end))
36     }
37 }

252ms

 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 intervalIntersection(_ A: [Interval], _ B: [Interval]) -> [Interval] {
14         if A.count == 0 || B.count == 0 { return [Interval]() }
15         var a = A
16         var b = B
17         a.reverse()
18         b.reverse()
19         var result = [Interval]()
20         var remaining = 0
21         while a.count > 0 && b.count > 0 {
22             var currA = a.removeLast()
23             var currB = b.removeLast()
24             if ((currB.end <= currA.end && currB.end >= currA.start) || 
25                 (currA.end <= currB.end && currA.end >= currB.start)) {
26                 if currA.end < currB.end {
27                     b.append(Interval(currA.end, currB.end))
28                 } else if currA.end > currB.end {
29                     a.append(Interval(currB.end, currA.end))
30                 }
31                 result.append(Interval(max(currA.start,currB.start), min(currA.end, currB.end)))
32             } else if currA.end < currB.start {
33                 b.append(currB) 
34             } else if currB.end < currA.start {
35                 a.append(currA) 
36             }
37         }
38         return result
39     }
40 }

272ms

 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 intervalIntersection(_ A: [Interval], _ B: [Interval]) -> [Interval] {
14         guard A.count > 0 && B.count > 0 else {
15             return []
16         }
17         
18         var combo = A
19         B.forEach { combo.append($0) }
20         combo.sort(by: { $0.start < $1.start })
21         var results = [Interval]()
22         var end = combo[0].end
23         for i in 1..<combo.count {
24             if combo[i].end < end {
25                 results.append(combo[i])
26             } else if combo[i].start <= end {
27                 results.append(Interval(combo[i].start, end))
28                 end = combo[i].end
29             } else {
30                 end = combo[i].end
31             }
32         }
33         return results
34     }
35 }

1472 ms

 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 intervalIntersection(_ A: [Interval], _ B: [Interval]) -> [Interval] {
14         if A.isEmpty || B.isEmpty {return []}
15         var C:[Interval] = [Interval](repeating:Interval(0,1),count:A.count*B.count)
16         var p:Int = 0
17         for x in A
18         {
19             for y in B
20             {
21                 var l:Int = max(x.start, y.start)
22                 var r:Int = min(x.end, y.end)
23                 if l <= r
24                 {
25                     C[p] = Interval(l, r)
26                     p += 1
27                 }
28             }
29         }
30         if (p - 1) < C.count
31         {
32             var arr = C[0...(p - 1)]
33             return [Interval](arr)
34         }
35         return C
36     }
37 }