2024/09/27 Leetcode Daily Problem

731. My Calendar II
難度: 中等

題意

如同昨天的[9/26] 查詢區間，但允許重疊一次!
實作一個MyCalendar的類，包含以下操作

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

思路1

如同昨天的[9/26] 查詢區間；建立兩個map，一個存重疊兩個的區間，一個存無重疊的區間。
這次每插入新區間，就先檢查重疊兩個，如果有蓋到則無法再插入。
再檢查無重疊並更新重疊兩個``無重疊。

實作1

class MyCalendarTwo
{
private:
    // Hash Map: start -> end
    // Store the [start, end) with one event
    map<int, int> event_1;
    // Store the [start, end) with two event
    map<int, int> event_2;

public:
    MyCalendarTwo()
    {
        event_1 = map<int, int>{}; // single-booking
        event_2 = map<int, int>{}; // double-booking
    }

    bool book(int start, int end)
    {
        // Check if overlap to double-booking
        map<int, int>::iterator lb_2 = event_2.lower_bound(start);
        if(lb_2 != event_2.end() && lb_2->first < end)
            return false;
        if(lb_2 != event_2.begin() && prev(lb_2)->second > start)
            return false;
        
        for(auto event : event_1)
        {
            int overlap_start = max(event.first, start);
            int overlap_end = min(event.second, end);
            if(overlap_start < overlap_end)
                event_2[overlap_start] = overlap_end;
        }
        event_1[start] = end;
        return true;
    }
};

結果1

錯了一個測資，乍看覺得應該要對得說。
Wrong Answer 96 / 97 test cases passed.
Input:

["MyCalendarTwo","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book"]
[[],[51,58],[77,85],[35,44],[53,61],[86,93],[55,61],[43,50],[64,69],[76,82],[98,100],[35,40],[25,32],[8,17],[37,43],[53,60],[86,91],[97,100],[37,43],[41,50],[83,92],[66,75],[42,48],[55,64],[37,46],[92,97],[69,76],[85,94],[60,66],[27,34],[36,44],[32,38],[56,62],[93,99],[11,18],[21,30],[81,89],[18,26],[81,90],[91,96],[43,49],[3,12],[97,100],[72,80],[15,23],[63,70],[8,16],[1,6],[16,24],[45,54],[3,9],[30,36],[29,35],[41,48],[21,26],[79,87],[27,32],[88,96],[47,55],[71,76],[32,40],[68,74],[51,59],[44,50],[65,71],[83,90],[86,94],[48,57],[26,32],[27,32],[78,83],[27,35],[19,24],[26,31],[67,75],[87,92],[6,15],[37,44],[62,68],[13,18],[41,46]]

實作2

先暫時不用二分搜法，直接用array存再遍歷檢查重疊:

class MyCalendarTwo
{
private:
    // Hash Map: start -> end
    // Store the [start, end) with one event
    vector<pair<int, int>> single_event;
    // Store the [start, end) with two event
    vector<pair<int, int>> double_event;

public:
    MyCalendarTwo()
    {
        single_event = vector<pair<int, int>>{};  // single-booking
        double_event = vector<pair<int, int>>{};  // double-booking
    }

    bool book(int start, int end)
    {
        for (auto event : double_event)
            if (event.first < end && event.second > start)
                return false;


        for (auto event : single_event)
        {
            if (event.first < end && event.second > start)
            {
                int overlapStart = max(event.first, start);
                int overlapEnd = min(event.second, end);
                double_event.push_back(make_pair(overlapStart, overlapEnd));
            }
        }

        single_event.push_back(make_pair(start, end));
        return true;
    }
};

結果2

Accepted
97/97 cases passed (66 ms)
Your runtime beats 94.68 % of cpp submissions
Your memory usage beats 90.93 % of cpp submissions (38 MB)

結果AC了，而且還不慢? 那昨的題還需要用二分搜嗎?XD

總結

今天腦袋昏昏，明天再來debug為甚麼二分搜會錯。