C++ optimal solution O(logN)


  • 0
    W

    Compare with My Calender I, we do two data struct :
    1. A ordered set of interval (start-end pair, sorted by start) is not enough. We use a map of {input interval => end of the other interval that overlaps it, if not overlapped using its own end}. With this data struct, if we insert a new interval, we only need to check the one before it to know whether there is any intervals before it will overlap the new interval.
    2. When overlap is found, insert the overlapped interval to a ordered set. When a new interval is inserted, we use the function in My Calender I to check whether the new interval overlaps any overlapped intevals. If true, then there will be 3-fold overlapping and the new interval should not be inserted. This check can guarantee that all the interval key in 1. can only overlap once and thus valid.

    class MyCalendarTwo {
        multimap<pair<int,int>,int> intervals;
        multiset<pair<int,int>> overlaps;
    public:
        MyCalendarTwo() {
            
        }
        bool validate(int start, int end) {
            auto p = make_pair(start, end);
            bool overlap = false;
            auto it = overlaps.insert(p);
            if (it != overlaps.begin()) {
                auto pp = prev(it);
                if (pp->second>start)
                    overlap = true;
            }
            if (it != prev(overlaps.end())) {
                auto pp = next(it);
                if (pp->first<end)
                    overlap = true;
            }
            overlaps.erase(it);
            return overlap;
        }
      
        bool book(int start, int end) {
            if (validate(start, end))
                return false;
            auto p = make_pair(start, end);
            // the input interval is valid, should be inserted
            auto it = intervals.insert(make_pair(p,end));
    	    // update the overlaped intervals created by current interval and intervals BEFORE it
            if (it != intervals.begin()) {
                auto pp = prev(it);
                if (pp->second > start) {
                    auto new_overlap = make_pair(start, min(pp->second, end));
                    overlaps.insert(new_overlap);
                }
                it->second = max(pp->second, end); // update the end of interval that overlaps inserted interval
            }
    	    // update the overlaped intervals created by current interval and intervals AFTER it
            auto nxt = next(it);
            while (nxt!=intervals.end() && nxt->first.first<end) {
                auto new_overlap = make_pair(nxt->first.first, min(end, nxt->first.second));
                overlaps.insert(new_overlap);
                nxt->second = max(nxt->second, end);
                nxt = next(nxt);
            }
            return true;      
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.