729. My Calendar I | Swift | Aug LeetCoding Challenge 2022

題目

2022/8/3 ，Aug LeetCoding Challenge 2022 的題目

• 題目： https://leetcode.com/problems/my-calendar-i/
• 難度： Medium

思路

• 需要排序
• 需要快速查找, 同時
  • 找到位置左邊的 end 不能大於 given start
  • 找到位置的 start 不能小於 given end

資料結構與演算法

• 排序陣列 - 有排序陣列就可以用 binary search 快速查找

問題點

插入陣列尾端後再重新排列會花較多時間，因此可以在 binary search 找到對應位置之後直接插入，就可以省下一次排序的計算。

程式碼

class MyCalendar {
    var events = [(start: Int, end: Int)]()
    
    init() { }
    
    func book(_ start: Int, _ end: Int) -> Bool {
        // ① Base case
        if events.isEmpty {
            events.append((start, end))
            return true
        }
        
        var left = 0
        var right = events.count - 1
        
        // ② 透過 binary search 找到跟 given start 最接近的位置
        while left <= right {
            let mid = (right + left) / 2
            if events[mid].start < start {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        // ③ 如果 start 小於前一個 event 的結束時間就可以 return false
        if left > 0 {
            if start < events[left - 1].end {
                return false 
            }
        }

        // ③ 如果 end 大於目前的 event 的開始時間就可以 return false
        if left < events.count {
            if end > events[left].start {
                return false 
            }
        }

        // ④ 有符合條件，插入 left 位置並回傳 true
        events.insert((start, end), at: left)
        return true
    }   
}

分析

• N - book 方法被呼叫的次數

時間複雜度

O(N*logN)

N 是呼叫次數，乘上每一次的執行 binary search 所需要的 logN

空間複雜度

O(N)