题目形容
这是 LeetCode 上的 729. 我的日程安排表 I，难度为 中等 。
Tag :「模仿」、「红黑树」、「线段树（动静开点）」、「线段树」、「分块」、「位运算」、「哈希表」
实现一个 MyCalendar 类来寄存你的日程安排。如果要增加的日程安排不会造成 反复预订，则能够存储这个新的日程安排。
当两个日程安排有一些工夫上的穿插时（例如两个日程安排都在同一时间内），就会产生 反复预订。
日程能够用一对整数 start 和 end 示意，这里的工夫是半开区间，即 $[start, end)$, 实数 $x$ 的范畴为，$start <= x < end$。
实现 MyCalendar 类：
MyCalendar()初始化日历对象。boolean book(int start, int end)如果能够将日程安排胜利增加到日历中而不会导致反复预订，返回true。否则，返回false并且不要将该日程安排增加到日历中。
示例：
输出：["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输入：[null, true, false, true]
解释：MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False，这个日程安排不能增加到日历中，因为工夫 15 曾经被另一个日程安排预订了。myCalendar.book(20, 30); // return True，这个日程安排能够增加到日历中，因为第一个日程安排预订的每个工夫都小于 20，且不蕴含工夫 20。提醒：
- $0 <= start < end <= 10^9$
- 每个测试用例，调用
book办法的次数最多不超过 $1000$ 次。
模仿
利用 book 操作最多调用 $1000$ 次，咱们能够应用一个数组存储所有已被预约的日期 $[start, end – 1]$，对于每次 book 操作，查看以后传入的 $[start, end)$ 是否会与已有的日期抵触，抵触返回 False，否则将 $[start, end- 1]$ 插入数组并返回 True。
代码：
class MyCalendar {List<int[]> list = new ArrayList<>();
public boolean book(int start, int end) {
end--;
for (int[] info : list) {int l = info[0], r = info[1];
if (start > r || end < l) continue;
return false;
}
list.add(new int[]{start, end});
return true;
}
}- 工夫复杂度：令 $n$ 为
book的最大调用次数，复杂度为 $O(n^2)$ - 空间复杂度：$O(n)$
线段树（动静开点）
线段树保护的节点信息包含：
ls/rs: 别离代表以后节点的左右子节点在线段树数组tr中的下标；add: 懒标记；val: 为以后区间的所蕴含的点的数量。
对于惯例的线段树实现来说，都是一开始就调用 build 操作创立空树，而线段树个别以「满二叉树」的模式用数组存储，因而须要 $4 * n$ 的空间，并且这些空间在起始 build 空树的时候曾经锁死。
如果一道题仅仅是「值域很大」的离线题（提前通晓所有的询问），咱们还能通过「离散化」来进行解决，将值域映射到一个小空间去，从而解决 MLE 问题。
但对于本题而言，因为「强制在线」的起因，咱们无奈进行「离散化」，同时值域大小达到 $1e9$ 级别，因而如果咱们想要应用「线段树」进行求解，只能采取「动静开点」的形式进行。
动静开点的劣势在于，不须要事先结构空树，而是在插入操作 add 和查问操作 query 时依据拜访须要进行「开点」操作。因为咱们不保障查问和插入都是间断的，因而对于父节点 $u$ 而言，咱们不能通过 u << 1 和 u << 1 | 1 的固定形式进行拜访，而要将节点 $tr[u]$ 的左右节点所在 tr 数组的下标进行存储，别离记为 ls 和 rs 属性。对于 $tr[u].ls = 0$ 和 $tr[u].rs = 0$ 则是代表子节点尚未被创立，当须要拜访到它们，而又尚未创立的时候，则将其进行创立。
因为存在「懒标记」，线段树的插入和查问都是 $\log{n}$ 的，因而咱们在单次操作的时候，最多会创立数量级为 $\log{n}$ 的点，因而空间复杂度为 $O(m\log{n})$，而不是 $O(4 * n)$，而开点数的预估需不能仅仅依据 $\log{n}$ 来进行，还要对常熟进行剖析，能力失去精确的点数上界。
动静开点相比于原始的线段树实现，实质仍是应用「满二叉树」的模式进行存储，只不过是按需创立区间，如果咱们是依照间断段进行查问或插入，最坏状况下依然会占到 $4 * n$ 的空间，因而盲猜 $\log{n}$ 的常数在 $4$ 左右，激进一点能够间接估算到 $6$，因而咱们能够估算点数为 $6 * m * \log{n}$，其中 $n = 1e9$ 和 $m = 1e3$ 别离代表值域大小和查问次数。
当然一个比拟实用的估点形式能够「尽可能的多开点数」，利用题目给定的空间上界和咱们创立的自定义类（构造体）的大小，尽可能的多开（Java 的 $128M$ 能够开到 $5 * 10^6$ 以上）。
代码：
class MyCalendar {
class Node {
// ls 和 rs 别离代表以后节点的左右子节点在 tr 的下标
// val 代表以后节点有多多数
// add 为懒标记
int ls, rs, add, val;
}
int N = (int)1e9, M = 120010, cnt = 1;
Node[] tr = new Node[M];
void update(int u, int lc, int rc, int l, int r, int v) {if (l <= lc && rc <= r) {tr[u].val += (rc - lc + 1) * v;
tr[u].add += v;
return ;
}
lazyCreate(u);
pushdown(u, rc - lc + 1);
int mid = lc + rc >> 1;
if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
pushup(u);
}
int query(int u, int lc, int rc, int l, int r) {if (l <= lc && rc <= r) return tr[u].val;
lazyCreate(u);
pushdown(u, rc - lc + 1);
int mid = lc + rc >> 1, ans = 0;
if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
return ans;
}
void lazyCreate(int u) {if (tr[u] == null) tr[u] = new Node();
if (tr[u].ls == 0) {tr[u].ls = ++cnt;
tr[tr[u].ls] = new Node();}
if (tr[u].rs == 0) {tr[u].rs = ++cnt;
tr[tr[u].rs] = new Node();}
}
void pushdown(int u, int len) {tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
tr[tr[u].ls].val += (len - len / 2) * tr[u].add; tr[tr[u].rs].val += len / 2 * tr[u].add;
tr[u].add = 0;
}
void pushup(int u) {tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
}
public boolean book(int start, int end) {if (query(1, 1, N + 1, start + 1, end) > 0) return false;
update(1, 1, N + 1, start + 1, end, 1);
return true;
}
}- 工夫复杂度：令 $n$ 为值域大小，本题固定为 $1e9$，线段树的查问和减少复杂度均为 $O(\log{n})$
- 空间复杂度：令询问数量为 $m$，复杂度为 $O(m\log{n})$
分块 + 位运算（分桶）
另一个留有遗憾的算法是「分块」，奢侈的分块做法是应用一个布尔数组 region 代表某个块是否有被占用，应用哈希表记录具体某个地位是否被占用，但惋惜被奇怪的测评机制卡了。
TLE 代码：
class MyCalendar {
static Boolean T = Boolean.TRUE, F = Boolean.FALSE;
static int n = (int)1e9, len = (int) Math.sqrt(n) + 30;
static boolean[] region = new boolean[len];
static Map<Integer, Boolean> map = new HashMap<>();
int getIdx(int x) {return x / len;}
void add(int l, int r) {if (getIdx(l) == getIdx(r)) {for (int k = l; k <= r; k++) map.put(k, T);
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) map.put(j++, T);
while (getIdx(i) == getIdx(r)) map.put(i--, T);
for (int k = getIdx(j); k <= getIdx(i); k++) region[k] = true;
}
}
boolean query(int l, int r) {if (getIdx(l) == getIdx(r)) {boolean cur = region[getIdx(l)];
for (int k = l; k <= r; k++) {if (map.getOrDefault(k, F) || cur) return false;
}
return true;
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) {if (map.getOrDefault(j, F) || region[getIdx(j)]) return false;
j++;
}
while (getIdx(i) == getIdx(r)) {if (map.getOrDefault(i, F) || region[getIdx(i)]) return false;
i--;
}
for (int k = getIdx(j); k <= getIdx(i); k++) {if (region[k]) return false;
}
return true;
}
}
public MyCalendar() {Arrays.fill(region, false);
map.clear();}
public boolean book(int start, int end) {if (query(start, end - 1)) {add(start, end - 1);
return true;
}
return false;
}
} 但咱们晓得分块算法的复杂度并不蹩脚，而哈希表可能是被卡常数的要害，因而咱们能够应用 int 数组来充当哈希表，因为只须要记录「是否被占用」，因而咱们能够应用 int 的每一位充当格子，通过这种「分桶 + 位运算」，无效升高常数。
AC 代码（2022-07-05 可过）：
class MyCalendar {static int n = (int)1e9, len = (int) Math.sqrt(n) + 50, cnt = 32;
static boolean[] region = new boolean[len];
static int[] map = new int[n / cnt];
int getIdx(int x) {return x / len;}
boolean get(int x) {return ((map[x / cnt] >> (x % cnt)) & 1) == 1;
}
void set(int x) {map[x / cnt] |= (1 << (x % cnt));
}
void add(int l, int r) {if (getIdx(l) == getIdx(r)) {for (int k = l; k <= r; k++) set(k);
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) set(j++);
while (getIdx(i) == getIdx(r)) set(i--);
for (int k = getIdx(j); k <= getIdx(i); k++) region[k] = true;
}
}
boolean query(int l, int r) {if (getIdx(l) == getIdx(r)) {boolean cur = region[getIdx(l)];
for (int k = l; k <= r; k++) {if (get(k) || cur) return false;
}
return true;
} else {
int j = l, i = r;
while (getIdx(j) == getIdx(l)) {if (get(j) || region[getIdx(j)]) return false;
j++;
}
while (getIdx(i) == getIdx(r)) {if (get(i) || region[getIdx(i)]) return false;
i--;
}
for (int k = getIdx(j); k <= getIdx(i); k++) {if (region[k]) return false;
}
return true;
}
}
public MyCalendar() {Arrays.fill(region, false);
Arrays.fill(map, 0);
}
public boolean book(int start, int end) {if (query(start, end - 1)) {add(start, end - 1);
return true;
}
return false;
}
}- 工夫复杂度：$O(n\sqrt{m})$
- 空间复杂度：$O(\sqrt{m} + \frac{M}{k})$，其中 $M = 1e9$ 为值域大小，$k = 32$ 为单个数字的可能存储的格子数
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.729 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布