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

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

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

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

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

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

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

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 }