傳送門：https://leetcode-cn.com/problems/my-calendar-iii/

一、題目描述

實現一個 MyCalendar 類來存放你的日程安排，你可以一直添加新的日程安排。

MyCalendar 有一個 book(int start, int end)方法。它意味著在start到end時間內增加一個日程安排，注意，這里的時間是半開區間，即 [start, end), 實數 x 的范圍為， start <= x < end。

當 K 個日程安排有一些時間上的交叉時（例如K個日程安排都在同一時間內），就會產生 K 次預訂。

每次調用 MyCalendar.book方法時，返回一個整數 K ，表示最大的 K 次預訂。

請按照以下步驟調用MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

二、示例

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

解釋

前兩個日程安排可以預訂并且不相交，所以最大的K次預訂是1。
第三個日程安排[10,40]與第一個日程安排相交，最高的K次預訂為2。
其余的日程安排的最高K次預訂僅為3。
請注意，最后一次日程安排可能會導致局部最高K次預訂為2，但答案仍然是3，原因是從開始到最后，時間[10,20]，[10,40]和[5,15]仍然會導致3次預訂。

說明

每個測試用例，調用 MyCalendar.book 函數最多不超過 400次。
調用函數 MyCalendar.book(start, end)時， start 和 end 的取值范圍為 [0, 10^9]。

三、分析

只考慮，起始點和結束點，即有向邊，不關注起始點或結束點之間的數據。添加新的行程時，起始點出度+1，結束點入度+1，找到整個數軸上出度最大的點就是被覆蓋次數最多的點。

四、實現

class MyCalendarThree { public:MyCalendarThree() {maximum = 0;}int book(int start, int end) {int k = 0;++m[start];--m[end];for (auto i = m.begin(); i != m.end(); ++i) {k+= i->second;if (maximum < k) maximum = k;}return maximum;}map<int, int> m;int maximum; };/*** Your MyCalendarThree object will be instantiated and called as such:* MyCalendarThree obj = new MyCalendarThree();* int param_1 = obj.book(start,end);*/ 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【LeetCode】732. 我的日程安排表 III的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。