leetcode731_go_我的日程安排表II

題目

實現一個 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）

示例：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 函式最多不超過 1000次。

呼叫函式 MyCalendar。book（start， end）時， start 和 end 的取值範圍為 ［0， 10^9］。

解題思路分析

1、雙陣列；時間複雜度O（n^2），空間複雜度O（n）

type MyCalendarTwo struct { first ［］［2］int second ［］［2］int}func Constructor（） MyCalendarTwo { return MyCalendarTwo{}}func （this *MyCalendarTwo） Book（start int， end int） bool { for i ：= 0； i < len（this。second）； i++ { a， b ：= this。second［i］［0］， this。second［i］［1］ if start < b && end > a { // 跟第二個重複 return false } } for i ：= 0； i < len（this。first）； i++ { a， b ：= this。first［i］［0］， this。first［i］［1］ if start < b && end > a { // 插入重疊的部分 this。second = append（this。second， ［2］int{max（start， a）， min（end， b）}） } } this。first = append（this。first， ［2］int{start， end}） return true}func max（a， b int） int { if a > b { return a } return b}func min（a， b int） int { if a > b { return b } return a}

總結

Medium題目，使用雙陣列來解決