2024/09/26 Leetcode Daily Problem

729. My Calendar I
難度: 中等

題意

實作一個MyCalendar的類，包含以下操作

1. MyCalendar()初始化這個類
2. boolean book(int start, int end)，插入左閉右開區間時間段[start, end)，並回傳true；若此時間段與已插入的時間段重疊則回傳false

思路

每插入一個時間段就按照其start排序好，接著每插入的的新時間段[start, end)

1. 查詢排在start之後的第一個時間段lower_bound，檢查lower_bound的start是否與新時間段的end重疊。若重疊則直接回傳false。
2. 查詢lower_bound的前一個時間段prev，檢查prev的end是否與新時間段的start重疊。若重疊則直接回傳false。
3. 若lower_bound, prev不存在，或前兩點都沒有重疊，則插入新時間段，回傳true。

實作

優先挑選能插入後自動排序的資料結構(std::set<pair<int, int>>或map<int, int>)
並用二分搜的技巧搜尋到lower_bound。
這裡主要是邊查邊學std::map::lower_bound(k)這個operator。

class MyCalendar
{
private:
    // Start -> End
    map<int, int> mp;

public:
    MyCalendar()
    {
        mp = map<int, int>{};
    }

    bool book(int start, int end)
    {
        // Returns an iterator pointing to the first element 
        // in the container whose key is not considered to go before k
        map<int, int>::iterator key_lower_it = mp.lower_bound(start);
        
        // Check overlap
        if (key_lower_it != mp.end() && key_lower_it->first < end)
            return false;
        if (key_lower_it != mp.begin() && prev(key_lower_it)->second > start)
            return false;

        mp[start] = end;
        return true;
    }
};

分析

若book次數為N。
根據std::map::insert()，每次O(logN)。
根據std::map::lower_bound()，每次O(logN)。
時間複雜度: O(NlogN)，插入N個，二分搜N次。
空間複雜度: O(N)，共N對start->end。

結果

Accepted
107/107 cases passed (68 ms)
Your runtime beats 88.62 % of cpp submissions
Your memory usage beats 59.1 % of cpp submissions (42.7 MB)

總結