★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：?https://www.cnblogs.com/strengthen/p/10620179.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Implement a?MyCalendarThree?class to store your events. A new event can?always?be added.

Your class will have one method,?book(int start, int end). Formally, this represents a booking on the half open interval?[start, end), the range of real numbers?x?such that?start <= x < end.

A?K-booking?happens when?K?events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method?MyCalendar.book, return an integer?K?representing the largest integer such that there exists a?K-booking in the calendar.

Your class will be called like this:?MyCalendarThree cal = new MyCalendarThree();MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree(); MyCalendarThree.book(10, 20); // returns 1 MyCalendarThree.book(50, 60); // returns 1 MyCalendarThree.book(10, 40); // returns 2 MyCalendarThree.book(5, 15); // returns 3 MyCalendarThree.book(5, 10); // returns 3 MyCalendarThree.book(25, 55); // returns 3 Explanation: The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking. The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking. The remaining events cause the maximum K-booking to be only a 3-booking. Note that the last event locally causes a 2-booking, but the answer is still 3 because eg. [10, 20), [10, 40), and [5, 15) are still triple booked.?

Note:

• The number of calls to?MyCalendarThree.book?per test case will be at most?400.
• In calls to?MyCalendarThree.book(start, end),?start?and?end?are integers in the range?[0, 10^9].

---

實現一個?MyCalendar?類來存放你的日程安排，你可以一直添加新的日程安排。

MyCalendar?有一個?book(int start, int end)方法。它意味著在start到end時間內增加一個日程安排，注意，這里的時間是半開區間，即?[start, end), 實數?x?的范圍為， ?start <= x < end。

當?K?個日程安排有一些時間上的交叉時（例如K個日程安排都在同一時間內），就會產生?K?次預訂。

每次調用?MyCalendar.book方法時，返回一個整數?K?，表示最大的?K?次預訂。

請按照以下步驟調用MyCalendar?類:?MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

示例 1:

MyCalendarThree(); MyCalendarThree.book(10, 20); // returns 1 MyCalendarThree.book(50, 60); // returns 1 MyCalendarThree.book(10, 40); // returns 2 MyCalendarThree.book(5, 15); // returns 3 MyCalendarThree.book(5, 10); // returns 3 MyCalendarThree.book(25, 55); // returns 3 解釋: 前兩個日程安排可以預訂并且不相交，所以最大的K次預訂是1。 第三個日程安排[10,40]與第一個日程安排相交，最高的K次預訂為2。 其余的日程安排的最高K次預訂僅為3。 請注意，最后一次日程安排可能會導致局部最高K次預訂為2，但答案仍然是3，原因是從開始到最后，時間[10,20]，[10,40]和[5,15]仍然會導致3次預訂。

說明:

• 每個測試用例，調用?MyCalendar.book?函數最多不超過?400次。
• 調用函數?MyCalendar.book(start, end)時，?start?和?end?的取值范圍為?[0, 10^9]。

---

524ms

1 class MyCalendarThree { 2 var s = [Int]() 3 var e = [Int]() 4 init() { 5 6 } 7 8 func book(_ start: Int, _ end: Int) -> Int { 9 let startIndex = searchInsert(s, start) 10 s.insert(start, at: startIndex) 11 let endIndex = searchInsert(e, end) 12 e.insert(end, at: endIndex) 13 return helper(s, e) 14 } 15 16 private func helper(_ s: [Int], _ e: [Int]) -> Int { 17 var res = 0 18 var cur = 0 19 var i = 0, j = 0 20 while i < s.count && j < e.count { 21 if s[i] < e[j] { 22 i += 1 23 cur += 1 24 } else { 25 j += 1 26 cur -= 1 27 } 28 res = max(res, cur) 29 } 30 return res 31 } 32 33 private func searchInsert(_ nums: [Int], _ target: Int) -> Int { 34 var low = 0 35 var high = nums.count-1 36 while low <= high { 37 let middle = (low + high) / 2 38 if nums[middle] == target { 39 return middle 40 } else if nums[middle] > target { 41 high = middle - 1 42 } else { 43 low = middle + 1 44 } 45 } 46 return low 47 } 48 }

---

740ms

1 private extension Array where Element: Comparable { 2 private func binarySearchIndex(for element: Element) -> Int { 3 var min = 0 4 var max = count 5 while min < max { 6 let index = (min+max)/2 7 let other = self[index] 8 if other == element { 9 return index 10 } else if other < element { 11 min = index+1 12 } else { 13 max = index 14 } 15 } 16 return min 17 } 18 19 mutating func binaryInsert(_ element: Element) { 20 insert(element, at: binarySearchIndex(for: element)) 21 } 22 } 23 24 class MyCalendarThree { 25 private var k = 0 26 private var starts = [Int]() 27 private var ends = [Int]() 28 29 func book(_ start: Int, _ end: Int) -> Int { 30 starts.binaryInsert(start) 31 ends.binaryInsert(end) 32 var k = 0 33 var current = 0 34 var i = 0 35 var j = 0 36 let count = starts.count 37 while i < count && j < count { 38 if starts[i] < ends[j] { 39 current += 1 40 i += 1 41 } else { 42 current -= 1 43 j += 1 44 } 45 k = max(k, current) 46 } 47 return k 48 } 49 }

---

Runtime:?836 ms Memory Usage:?21.6 MB 1 class MyCalendarThree { 2 var root:TreeNode? = nil 3 4 init() { 5 root = TreeNode(0, 1000000000) 6 } 7 8 func book(_ start: Int, _ end: Int) -> Int { 9 add(root, start, end, 1) 10 return getMax(root) 11 } 12 13 func add(_ node:TreeNode?,_ start:Int,_ end:Int,_ val:Int) 14 { 15 if node == nil || start >= node!.end || end < node!.start 16 { 17 return 18 } 19 if start <= node!.start && node!.end <= end 20 { 21 node!.booked += val 22 node!.saved += val 23 return 24 } 25 var mid:Int = node!.start + (node!.end - node!.start) / 2 26 if overlap(node!.start, mid, start, end) 27 { 28 if node?.left == nil 29 { 30 node?.left = TreeNode(node!.start, mid) 31 } 32 add(node?.left, start, end, val) 33 } 34 if overlap(mid, node!.end, start, end) 35 { 36 if node?.right == nil 37 { 38 node?.right = TreeNode(mid, node!.end) 39 } 40 add(node?.right, start, end, val) 41 } 42 node!.saved = node!.booked + max(getMax(node?.left), getMax(node?.right)) 43 } 44 45 func getMax(_ node:TreeNode?) -> Int 46 { 47 if node == nil {return 0} 48 return node!.saved 49 } 50 51 func overlap(_ s:Int,_ e:Int,_ l:Int,_ r:Int) -> Bool 52 { 53 if r <= s || l >= e 54 { 55 return false 56 } 57 return true 58 } 59 } 60 61 class TreeNode 62 { 63 var start:Int 64 var end:Int 65 var left:TreeNode? = nil 66 var right:TreeNode? = nil 67 var booked:Int = 0 68 var saved:Int = 0 69 70 init(_ s:Int,_ t:Int) 71 { 72 self.start = s 73 self.end = t 74 } 75 }

---

844ms

1 class MyCalendarThree { 2 3 private var keys = [Int]() 4 private var increments = [Int]() 5 6 func book(_ start: Int, _ end: Int) -> Int { 7 var startIndex = 0 8 var endIndex = 0 9 var startExistedBefore = false 10 var endExistedBefore = false 11 var startDone = false 12 for index in 0 ..< keys.count { 13 let existingKey = keys[index] 14 if startDone == false { 15 if start == existingKey { 16 startDone = true 17 startExistedBefore = true 18 } else if start > existingKey { 19 startIndex += 1 20 } else { 21 startDone = true 22 } 23 } 24 if end > existingKey { 25 endIndex += 1 26 } else { 27 if end == existingKey { 28 endExistedBefore = true 29 } 30 break 31 } 32 } 33 if endIndex < keys.count { 34 if endExistedBefore { 35 increments[endIndex] -= 1 36 } else { 37 keys.insert(end, at: endIndex) 38 increments.insert(-1, at: endIndex) 39 } 40 } else { 41 keys.append(end) 42 increments.append(-1) 43 } 44 if startExistedBefore { 45 increments[startIndex] += 1 46 } else { 47 keys.insert(start, at: startIndex) 48 increments.insert(1, at: startIndex) 49 } 50 var maxBookings = 0 51 var currentBookings = 0 52 for increment in increments { 53 currentBookings += increment 54 maxBookings = max(maxBookings, currentBookings) 55 } 56 return maxBookings 57 } 58 }

---

852ms

1 private extension Array where Element: Comparable { 2 private func binarySearchIndex(for element: Element) -> Int { 3 var min = 0 4 var max = count 5 while min < max { 6 let index = (min+max)/2 7 let other = self[index] 8 if other == element { 9 return index 10 } else if other < element { 11 min = index+1 12 } else { 13 max = index 14 } 15 } 16 return min 17 } 18 19 mutating func binaryInsert(_ element: Element) { 20 insert(element, at: binarySearchIndex(for: element)) 21 } 22 } 23 24 class MyCalendarThree { 25 private var k = 0 26 private var points = [Point]() 27 28 private struct Point: Comparable { 29 let value: Int 30 let isStart: Bool 31 32 static func ==(lhs: Point, rhs: Point) -> Bool { 33 return lhs.value == rhs.value && lhs.isStart == rhs.isStart 34 } 35 36 static func <(lhs: Point, rhs: Point) -> Bool { 37 return lhs.value < rhs.value || (lhs.value == rhs.value && !lhs.isStart && rhs.isStart) 38 } 39 } 40 41 func book(_ start: Int, _ end: Int) -> Int { 42 points.binaryInsert(Point(value: start, isStart: true)) 43 points.binaryInsert(Point(value: end, isStart: false)) 44 var k = 0 45 var current = 0 46 for point in points { 47 current += (point.isStart ? 1 : -1) 48 k = max(k, current) 49 } 50 return k 51 } 52 }

---

1356ms

1 extension Array { 2 func insertionIndexOf(_ elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int { 3 var lo = 0 4 var hi = self.count - 1 5 while lo <= hi { 6 let mid = (lo + hi)/2 7 if isOrderedBefore(self[mid], elem) { 8 lo = mid + 1 9 } else if isOrderedBefore(elem, self[mid]) { 10 hi = mid - 1 11 } else { 12 return mid 13 } 14 } 15 return lo 16 } 17 } 18 19 class MyCalendarThree { 20 21 var books = [Int:Int]() 22 var sKeys = [Int]() 23 var unqKeys = [Int:Int]() 24 25 func book(_ start: Int, _ end: Int) -> Int { 26 27 books[start] = (books[start] ?? 0)+1 28 books[end] = (books[end] ?? 0)-1 29 insert(start) 30 insert(end) 31 32 var maxInt=0, acc=0 33 sKeys.forEach { intPoint in 34 acc += books[intPoint] ?? 0 35 if acc>maxInt {maxInt = acc} 36 } 37 return maxInt 38 } 39 40 func insert(_ element:Int) { 41 42 guard unqKeys[element]==nil else {return} 43 44 let newElement = element 45 // Or: myArray.indexOf(c, <) 46 let index = sKeys.insertionIndexOf(newElement) { $0 < $1 } 47 sKeys.insert(newElement, at: index) 48 unqKeys[newElement] = 1 49 } 50 }

---

1528ms

1 class MyCalendarThree { 2 private var k = 0 3 private var ranges = [(start: Int, end: Int, k: Int)]() 4 5 func book(_ start: Int, _ end: Int) -> Int { 6 var newRanges = [(start: Int, end: Int, k: Int)]() 7 var overlaps = [(start: Int, end: Int, k: Int)]() 8 for range in ranges { 9 if start >= range.end || range.start >= end { 10 newRanges.append(range) 11 } else { 12 if range.start < start { 13 newRanges.append((range.start, start, range.k)) 14 } 15 if end < range.end { 16 newRanges.append((end, range.end, range.k)) 17 } 18 let overlap = (start: max(start, range.start), end: min(end, range.end), k: range.k+1) 19 newRanges.append(overlap) 20 overlaps.append(overlap) 21 k = max(k, overlap.k) 22 } 23 } 24 var start = start 25 for overlap in overlaps.sorted(by: { $0.start < $1.start }) { 26 if start < overlap.start { 27 newRanges.append((start, overlap.start, 1)) 28 } 29 start = overlap.end 30 } 31 if start < end { 32 newRanges.append((start, end, 1)) 33 k = max(k, 1) 34 } 35 ranges = newRanges 36 return k 37 } 38 }

---

1804ms

1 struct SortedArray: Collection { 2 3 func index(after i: Int) -> Int {return elements.index(after: i)} 4 var startIndex: Int {return elements.startIndex} 5 var endIndex: Int {return elements.endIndex} 6 7 private var elements = [Int]() 8 private var uniqueIds = [Int:Int]() 9 var count: Int {return elements.count} 10 11 private func insertionIndexOf(_ element:Int, isOrderedBefore:(Int,Int)->Bool) -> Int { 12 var left=0 13 var right=elements.count-1 14 while left<=right { 15 let mid = (left+right)/2 16 if isOrderedBefore(elements[mid], element) {left = mid+1} 17 else if isOrderedBefore(element, elements[mid]) {right = mid-1} 18 else{return mid} //ideally, will never execute as element doesn't exist yet 19 } 20 return left 21 } 22 23 public subscript(i: Int) -> Int { 24 // guard i >= 0 && i < elements.count else {return nil} 25 return self.elements[i] 26 } 27 28 mutating func insert(_ element:Int) { 29 guard uniqueIds[element]==nil else {return} 30 let index = insertionIndexOf(element) {$0<$1} 31 elements.insert(element, at: index) 32 uniqueIds[element] = 1 33 } 34 } 35 36 class MyCalendarThree { 37 38 var books = [Int:Int]() 39 var sKeys = SortedArray() 40 41 func book(_ start: Int, _ end: Int) -> Int { 42 43 books[start] = (books[start] ?? 0)+1 44 books[end] = (books[end] ?? 0)-1 45 sKeys.insert(start) 46 sKeys.insert(end) 47 48 var maxInt=0, acc=0 49 for intPoint in sKeys { 50 // guard let intPoint=intPoint else{continue} 51 acc += books[intPoint] ?? 0 52 if acc>maxInt {maxInt = acc} 53 } 54 return maxInt 55 } 56 }

---

3376ms

1 class MyCalendarThree { 2 private var k = 0 3 private var points = [(point: Int, isStart: Bool)]() 4 5 func book(_ start: Int, _ end: Int) -> Int { 6 points.append((start, true)) 7 points.append((end, false)) 8 points.sort(by: { $0.point == $1.point ? !$0.isStart : $0.point < $1.point }) 9 var k = 0 10 var current = 0 11 for (_, isStart) in points { 12 current += (isStart ? 1 : -1) 13 k = max(k, current) 14 } 15 return k 16 } 17 }

?

?

轉載于:https://www.cnblogs.com/strengthen/p/10620179.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Swift]LeetCode732. 我的日程安排表 III | My Calendar III的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。