731. My Calendar II
難度: 中等
如同昨天的[9/26] 查詢區間,但允許重疊一次!
實作一個MyCalendar
的類,包含以下操作
boolean book(int start, int end)
,插入左閉右開區間時間段[start, end),並回傳true
;若此時間段與已插入的時間段重疊超過兩次則回傳false
。如同昨天的[9/26] 查詢區間;建立兩個map,一個存重疊兩個
的區間,一個存無重疊
的區間。
這次每插入新區間,就先檢查重疊兩個
,如果有蓋到則無法再插入。
再檢查無重疊
並更新重疊兩個``無重疊
。
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;
}
};
錯了一個測資,乍看覺得應該要對得說。
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]]
先暫時不用二分搜法,直接用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;
}
};
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為甚麼二分搜會錯。
Time Submitted | Status | Runtime | Memory | Language |
---|---|---|---|---|
09/27/2024 22:36 | Accepted | 66 ms | 38 MB | cpp |
09/27/2024 22:19 | Wrong Answer | N/A | N/A | cpp |
09/27/2024 21:35 | Wrong Answer | N/A | N/A | cpp |