[Swift]LeetCode731. 我的日程安排表 II | My Calendar II

it2022-05-06 1

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

Implement a MyCalendarTwoclass to store your events. A new event can be added if adding the event will not cause a triplebooking.

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 triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

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

Example 1:

MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(50, 60); // returns true MyCalendar.book(10, 40); // returns true MyCalendar.book(5, 15); // returns false MyCalendar.book(5, 10); // returns true MyCalendar.book(25, 55); // returns true Explanation: The first two events can be booked. The third event can be double booked. The fourth event (5, 15) can't be booked, because it would result in a triple booking. The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked. The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event; the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.In calls to MyCalendar.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。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例 1:

MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(50, 60); // returns true MyCalendar.book(10, 40); // returns true MyCalendar.book(5, 15); // returns false MyCalendar.book(5, 10); // returns true MyCalendar.book(25, 55); // returns true 解释: 前两个日程安排可以添加至日历中。第三个日程安排会导致双重预订，但可以添加至日历中。第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。

说明:

每个测试用例，调用 MyCalendar.book 函数最多不超过 100次。调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。

728ms

1 class MyCalendarTwo { 2 typealias Interval = (start: Int, end: Int) 3 var intervals: [Interval] = [] 4 var overlaps: [Interval] = [] 5 init() { 6 7 } 8 9 func book(_ start: Int, _ end: Int) -> Bool { 10 for overlap in overlaps { 11 if overlap.start < end, overlap.end > start { 12 return false 13 } 14 } 15 for interval in intervals { 16 if interval.start < end, interval.end > start { 17 overlaps.append((max(interval.start, start), min(interval.end, end))) 18 } 19 } 20 intervals.append((start, end)) 21 22 return true 23 } 24 } 25 /** 26 * Your MyCalendarTwo object will be instantiated and called as such: 27 * let obj = MyCalendarTwo() 28 * let ret_1: Bool = obj.book(start, end) 29 */

Runtime: 748 ms Memory Usage: 20.1 MB 1 class MyCalendarTwo { 2 var s1:[(Int,Int)] 3 var s2:[(Int,Int)] 4 5 init() { 6 s1 = [(Int,Int)]() 7 s2 = [(Int,Int)]() 8 } 9 10 func book(_ start: Int, _ end: Int) -> Bool { 11 for ele in s2 12 { 13 if start >= ele.1 || end <= ele.0 14 { 15 continue 16 } 17 else 18 { 19 return false 20 } 21 } 22 for ele in s1 23 { 24 if start >= ele.1 || end <= ele.0 25 { 26 continue 27 } 28 else 29 { 30 s2.append((max(start, ele.0), min(end, ele.1))) 31 } 32 } 33 s1.append((start, end)) 34 return true; 35 } 36 } 37 38 /** 39 * Your MyCalendarTwo object will be instantiated and called as such: 40 * let obj = MyCalendarTwo() 41 * let ret_1: Bool = obj.book(start, end) 42 */

852ms

1 class MyCalendarTwo { 2 var books = [(start: Int, end: Int)]() 3 var doubles = [(start: Int, end: Int)]() 4 5 func book(_ start: Int, _ end: Int) -> Bool { 6 7 for double in doubles { 8 if start<double.end && end>double.start { 9 return false 10 } 11 } 12 13 for book in books { 14 if start<book.end && end>book.start { 15 let double = (max(start, book.start),min(end, book.end)) 16 doubles.append(double) 17 } 18 } 19 20 books.append((start,end)) 21 return true 22 } 23 }

1596ms

1 import Foundation 2 3 class MyCalendarTwo { 4 5 public var events1: [(Int, Int)] 6 public var events2: [(Int, Int)] 7 8 init() { 9 events1 = [(Int, Int)]() 10 events2 = [(Int, Int)]() 11 } 12 13 func book(_ start: Int, _ end: Int) -> Bool { 14 guard start < end else { return false } 15 guard start >= 0 && start <= 1000000000 else { return false } 16 guard end >= 0 && end <= 1000000000 else { return false } 17 18 var newEvent = (start, end) 19 // backup 20 let _events1 = events1 21 let _events2 = events2 22 23 var offset = 0; 24 25 // Check events1 26 for (i, event) in events1.enumerated() { 27 // left, prepend 28 if newEvent.1 <= event.0 { 29 events1.insert(newEvent, at: i + offset) 30 offset += 1 31 return true 32 } 33 34 // right 35 if newEvent.0 >= event.1 { continue } 36 37 // intersection 38 if newEvent.0 < event.0 { 39 // partial, insert left part 40 events1.insert((newEvent.0, event.0), at: i + offset) 41 offset += 1 42 newEvent.0 = event.0 43 } 44 45 if newEvent.1 <= event.1 { 46 // overlap, check all, double book 47 guard book2(newEvent) else { 48 events1 = _events1 49 events2 = _events2 50 return false 51 } 52 return true 53 } else { 54 // partial, check left part, double book 55 guard book2(newEvent.0, event.1) else { 56 events1 = _events1 57 events2 = _events2 58 return false 59 } 60 newEvent.0 = event.1 61 } 62 } 63 64 // no insertion, append to the last 65 events1.append(newEvent) 66 return true 67 } 68 69 private func book2(_ start: Int, _ end: Int) -> Bool { 70 guard start < end else { return false } 71 guard start >= 0 && start <= 1000000000 else { return false } 72 guard end >= 0 && end <= 1000000000 else { return false } 73 74 let newEvent = (start, end) 75 76 return book2(newEvent) 77 } 78 79 private func book2(_ newEvent: (Int, Int)) -> Bool { 80 for (i, event) in events2.enumerated() { 81 guard newEvent.0 >= event.1 || newEvent.1 <= event.0 else { return false } 82 83 // left, prepend 84 if newEvent.1 <= event.0 { 85 events2.insert(newEvent, at: i) 86 return true 87 } 88 89 // right 90 if newEvent.0 >= event.1 { continue } 91 } 92 93 events2.append(newEvent) 94 return true 95 } 96 }

转载于:https://www.cnblogs.com/strengthen/p/10518918.html

相关资源：数据结构—成绩单生成器

专利

最新回复(0)