Let's make this one less mysterious. For 731. My Calendar II, the solution in this repository is mainly a data structure design solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design.
The notes already sitting in the source point us in the right direction:
- WA
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are book.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//WA
02class MyCalendarTwo {
03public:
04 multimap<int, int> sgl;
05 map<int, int> dbl;
06
07 MyCalendarTwo() {
08
09 }
10
11 bool book(int start, int end) {
12 auto it = dbl.upper_bound(start);
13 int prev = (it != dbl.begin()) ? (--it)->first : -1;
14 it = dbl.lower_bound(start);
15 int next = (it != dbl.end()) ? it->first : -1;
16
17 // if(prev == -1) cout << "-1 ";
18 // else cout << dbl[prev] << "<= ";
19 // cout << start << " <= " << end;
20 // if(next == -1) cout << " -1 ?" << endl;
21 // else cout << " <= " << next << " ?" << endl;
22
23 if((prev == -1 || dbl[prev] < start) &&
24 (next == -1 || end <= next)){
25 //update dbl
26 /*if current booking have no intersection with previous bookings in sgl,
27 then we don't need to update dbl,
28 o.w., we need to add their intersection into dbl
29 */
30 auto itPrev = sgl.upper_bound(start);
31 if(itPrev != sgl.begin()){
32 itPrev--;
33 }else{
34 itPrev = sgl.end();
35 }
36 auto itNext = sgl.lower_bound(start);
37 if(!((itPrev == sgl.end() || itPrev->second < start) &&
38 (itNext == sgl.end() || end <= itNext->first))){
39 //if there is an intersection
40 if(itPrev != sgl.end() && start < itPrev->second){
41 //intersect with previous
42 // cout << "[" << start << "," << end << ")" << " intersect with " << "[" << itPrev->first << ", " << itPrev->second << ")" << endl;
43 // cout << "[" << start << ", " << itPrev->second << ") in dbl." << endl;
44 dbl[start] = min(end, itPrev->second);
45 }
46 if(itNext != sgl.end() && itNext != itPrev && itNext->first < end){
47 //intersect with next
48 // cout << "[" << start << "," << end << ")" << " intersect with " << "[" << itNext->first << ", " << itNext->second << ")" << endl;
49 // cout << "[" << itNext->first << ", " << end << ") in dbl." << endl;
50 dbl[max(start, itNext->first)] = end;
51 }
52 }
53 //update sgl
54 sgl.insert({start, end});
55
56 for(auto it = sgl.begin(); it != sgl.end(); it++){
57 cout << it->first << " " << it->second << " | ";
58 }
59 cout << endl;
60
61 for(auto it = dbl.begin(); it != dbl.end(); it++){
62 cout << it->first << " " << it->second << " | ";
63 }
64 cout << endl;
65 return true;
66 }
67
68 for(auto it = sgl.begin(); it != sgl.end(); it++){
69 cout << it->first << " " << it->second << " | ";
70 }
71 cout << endl;
72
73 for(auto it = dbl.begin(); it != dbl.end(); it++){
74 cout << it->first << " " << it->second << " | ";
75 }
76 cout << endl;
77
78 return false;
79 }
80};
81
82/**
83 * Your MyCalendarTwo object will be instantiated and called as such:
84 * MyCalendarTwo* obj = new MyCalendarTwo();
85 * bool param_1 = obj->book(start,end);
86 */
87
88//Approach #1: Brute Force
89//Runtime: 216 ms, faster than 39.61% of C++ online submissions for My Calendar II.
90//Memory Usage: 31.3 MB, less than 100.00% of C++ online submissions for My Calendar II.
91//time: O(N^2), space: O(N)
92class MyCalendarTwo {
93public:
94 vector<vector<int>> sgl, dbl;
95
96 MyCalendarTwo() {
97
98 }
99
100 bool book(int start, int end) {
101 for(vector<int>& event : dbl){
102 if(event[0] < end && event[1] > start){
103 return false;
104 }
105 }
106 for(vector<int>& event : sgl){
107 if(event[0] < end && start < event[1]){
108 //current booking may overlap with multiple previous events, so no break here!
109 dbl.push_back({max(start, event[0]), min(end, event[1])});
110 }
111 }
112 sgl.push_back({start, end});
113 return true;
114 }
115};
116
117/**
118 * Your MyCalendarTwo object will be instantiated and called as such:
119 * MyCalendarTwo* obj = new MyCalendarTwo();
120 * bool param_1 = obj->book(start,end);
121 */Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.