leetcode 732. My Calendar III 我的日历 + 统计最大公共区间+ 使用Map记录出入度

太过爱你忘了你带给我的痛 2022-06-03 09:00 95阅读 0赞

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval \[start, end), the range of real numbers x such that start <= x < end.

A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree(); MyCalendarThree.book(start, end)  
Example 1:  
MyCalendarThree();  
MyCalendarThree.book(10, 20); // returns 1  
MyCalendarThree.book(50, 60); // returns 1  
MyCalendarThree.book(10, 40); // returns 2  
MyCalendarThree.book(5, 15); // returns 3  
MyCalendarThree.book(5, 10); // returns 3  
MyCalendarThree.book(25, 55); // returns 3  
Explanation:  
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.  
The third event \[10, 40) intersects the first event, and the maximum K-booking is a 2-booking.  
The remaining events cause the maximum K-booking to be only a 3-booking.  
Note that the last event locally causes a 2-booking, but the answer is still 3 because  
eg. \[10, 20), \[10, 40), and \[5, 15) are still triple booked.  
Note:

The number of calls to MyCalendarThree.book per test case will be at most 400.  
In calls to MyCalendarThree.book(start, end), start and end are integers in the range \[0, 10^9\].

本题题意很简单，就是说寻找覆盖次数最多为几次，网上看了这么的一个做法，十分的不错，

如果只是保存起始和终点的情况，而完全不管中间经过的点呢？  
类似于图， 线段可以看做是一条有向边， 每次从一个点A指向B,相当于A的出度+1， B的入度 + 1。 这种情况下， 找到整个数轴上出度最大的点就是被覆盖次数最多的点。

其实这个是利用C++的map是使用BST存储的，所以都是有序的

**这道题的做法十分的棒，是图的出度入度的一个很好的变形，很值得学习**

建议和[leetcode 729. My Calendar I][] 和 [leetcode 731. My Calendar II][] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class MyCalendarThree 
    {
    public:
        map<int, int> mmp;
        MyCalendarThree() 
        {
    
        }
    
        int book(int start, int end) 
        {
            mmp[start]++;
            mmp[end]--;
            int maxCount = 0 , sum = 0;
            for (auto a : mmp)
            {
                sum += a.second;
                if (sum > maxCount)
                    maxCount = sum;
            }
            return maxCount;
        }
    };
    
    /**
    * Your MyCalendarThree object will be instantiated and called as such:
    * MyCalendarThree obj = new MyCalendarThree();
    * int param_1 = obj.book(start,end);
    */

[leetcode 729. My Calendar I]: http://blog.csdn.net/jackzhang_123/article/details/78887019
[leetcode 731. My Calendar II]: http://blog.csdn.net/jackzhang_123/article/details/78887221