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.
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.
class MyCalendarThree {
private:
map mp;
public:
MyCalendarThree() {}
int book(int start, int end) {
++mp[start], --mp[end];
int result = 0, sum = 0;
for (auto it = mp.begin(); it != mp.end(); ++it) {
sum += it->second;
result = max(result, sum);
}
return result;
}
};
代码 2 [线段树]
class MyCalendarThree:
def __init__(self):
self.tree = defaultdict(int)
self.lazy = defaultdict(int)
def update(self, start: int, end: int, l: int, r: int, idx: int):
if r < start or end < l:
return
if start <= l and r <= end:
self.tree[idx] += 1
self.lazy[idx] += 1
else:
mid = (l + r) >> 1
self.update(start, end, l, mid, idx * 2)
self.update(start, end, mid + 1, end, idx * 2 + 1)
self.tree[idx] = self.lazy[idx] + max(self.tree[idx * 2], self.tree[idx * 2 + 1])
def book(self, start: int, end: int) -> int:
self.update(start, end - 1, 0, 10 ** 9, 1)
return self.tree[1]
2. 最大频率栈
Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.
Implement the FreqStack class:
- FreqStack() constructs an empty frequency stack.
- void push(int val) pushes an integer val onto the top of the stack.
- int pop() removes and returns the most frequent element in the stack.
- If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.
Input ["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output [null, null, null, null, null, null, null, 5, 7, 5, 4] Explanation FreqStack freqStack = new FreqStack(); freqStack.push(5); // The stack is [5] freqStack.push(7); // The stack is [5,7] freqStack.push(5); // The stack is [5,7,5] freqStack.push(7); // The stack is [5,7,5,7] freqStack.push(4); // The stack is [5,7,5,7,4] freqStack.push(5); // The stack is [5,7,5,7,4,5] freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4]. freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4]. freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4]. freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
Constraints:
- 0 <= val <= 10^9
- At most 2 * 10^4 calls will be made to push and pop.
- It is guaranteed that there will be at least one element in the stack before calling pop.
class FreqStack(object):
def __init__(self):
self.freq = collections.Counter()
self.group = collections.defaultdict(list)
self.maxfreq = 0
def push(self, x):
f = self.freq[x] + 1
self.freq[x] = f
if f > self.maxfreq:
self.maxfreq = f
self.group[f].append(x)
def pop(self):
x = self.group[self.maxfreq].pop()
self.freq[x] -= 1
if not self.group[self.maxfreq]:
self.maxfreq -= 1
return x
3. 将数据流变为多个不相交区间
给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类：
- SummaryRanges() 使用一个空数据流初始化对象。
- void addNum(int val) 向数据流中加入整数 val 。
- int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。
输入： ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] [[], [1], [], [3], [], [7], [], [2], [], [6], []] 输出： [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] 解释： SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
Constraints:
- 0 <= val <= 10^4
- 最多调用 addNum 和 getIntervals 方法 3 * 10^4 次
方法：有序哈希 + 位图
执行 void addNum(int val) 操作时具有以下两种情况：
- 情况一：val 在前序操作已经插入过，直接跳过；
- 情况二：val 在前序操作中没有出现过，此时直接新建一个区间 [val, val]，如果存在相邻区间，则合并这两个区间。
实现方法：
- 在情况一需要查找元素是否存在，情况二中需要查找相邻区间边界元素是否存在，因此可以用位图快速查找。
- 需要记录区间边界，可以采用有序哈希，对于区间 [left, right] ，可以使用 map[left]=right 和 map[right]=left 记录。
实现细节：
- 对于区间 [val, val] 需要考虑与 [left, val-1] 和 [val+1, right] 两个区间的合并情况，可以单独声明一个函数 void combine(int mi) 实现 [left, mi] 和 [mi+1, right] 区间的合并。
- 使用 bitset 时需要注意，bitset 中的元素必须不能为负数。
- 遍历 map 输出结果时，对于 pair
提交情况：
-
执行用时：40 ms, 在所有 C++ 提交中击败了96.24%的用户
-
内存消耗：32.4 MB, 在所有 C++ 提交中击败了62.10%的用户
class SummaryRanges {
private:
bitset<10000> bset; // 记录输入数据
map mp; // 记录元素上下边界
void combine(int mi) { // 合并区间 [left, mi], [mi+1, right]
int left = mp[mi], right = mp[mi + 1];
mp[left] = right, mp[right] = left;
if (mi != left) mp.erase(mi);
if (mi + 1 != right) mp.erase(mi + 1);
}
public:
SummaryRanges() {}
void addNum(int val) {
if (bset.test(val)) return; // 排除数据重复出现情况
bset.set(val);
mp[val] = val; // 设置单独区间 [val, val]
if (bset.test(val + 1)) combine(val); // 如果右侧区间存在, 合并 [val, val], [val+1, right]
if (val > 0 && bset.test(val - 1)) combine(val - 1); // 如果左侧区间存在, 合并 [left, val-1], [val, right]
}
vector> getIntervals() {
vector> result;
for (auto &it : mp) { // 遍历map, 输出结果
if (it.first <= it.second) result.push_back({it.first, it.second});
}
return result;
}
};
