My Calendar III Problem


Description

LeetCode Problem 732.

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

You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

  • MyCalendarThree() Initializes the object.
  • int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]
Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarThree.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

Constraints:

  • 0 <= start < end <= 10^9
  • At most 400 calls will be made to book.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MyCalendarThree {
    int maxCnt = 0;
    // key: time; val: +1 if start, -1 if end
    map<int, int> mp; 
    
public:    
    MyCalendarThree() {
        
    }
    
    int book (int start, int end) {
        mp[start] ++;
        mp[end] --;
        int cnt = 0;
        for (auto it = mp.begin(); it != mp.end(); it++) {
            cnt += it->second;
            maxCnt = max(cnt, maxCnt);
        }
        return maxCnt;   
    }
};
/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(start,end);
 */




Related Posts

Time Based Key-Value Store Problem

LeetCode 981. Design a time-based key-value data structure that can...

Rle Iterator Problem

LeetCode 900. We can use run-length encoding (i.e., RLE) to...

Online Stock Span Problem

LeetCode 901. Design an algorithm that collects daily price quotes...

Online Election Problem

LeetCode 911. You are given two integer arrays persons and...

Number Of Recent Calls Problem

LeetCode 933. You have a RecentCounter class which counts the...

Maximum Frequency Stack Problem

LeetCode 895. Design a stack-like data structure to push elements...