LeetCode 731. My Calendar II

https://leetcode.com/problems/my-calendar-ii/description/

題目大意

這題很像LeetCode 729. My Calendar I

思考

Algo 1

我們一樣用一個 map 但這次用的是時間跟次數的映射

class MyCalendarTwo
{
public:
    MyCalendarTwo() {}

    bool book(int start, int end)
    {
        ++events[start];
        --events[end];

        int booking = 0;
        for (const auto &event : events)
        {
            booking += event.second;
            if (!(booking < 3))
            {
                --events[start];
                ++events[end];
                return false;
            }
        }
        return true;
    }

private:
    map<int, int> events;
};

Algo 2

使用兩條 vector<pair<int, int>>

class MyCalendarTwo
{
public:
    MyCalendarTwo() {}

    bool book(int start, int end)
    {
        for (const auto &overlap : overlaps)
        {
            if (start < overlap.second && end > overlap.first)
                return false;
        }

        for (const auto &event : events)
        {
            if (start < event.second && end > event.first)
                overlaps.emplace_back(max(start, event.first), min(end, event.second));
        }

        events.emplace_back(start, end);
        return true;
    }

private:
    vector<pair<int, int>> events;
    vector<pair<int, int>> overlaps;
};

題目其實有說 At most 1000 calls will be made to book.

實際表現上 algo 2 也好了一點點