P2555. VLAN资源池

解题思路

用二元组表示区间

输入的第一行表示若干 VLAN 资源，如果用 , 进行分割，每个字符串有两种可能的情况：

• 单个数字，譬如 "5"
• 一个区间，譬如 "1-3"

如果用更加方便的 二元组形式 来表示区间，譬如 "1-3" 再用 - 进行分割后，容易转换为 (1, 3)。 为了保持数据的一致性，对于单个数字的情况，也可以用二元组来表示，譬如 "5" 用 (5, 5) 来表示。

因此，可以构建出如下的代码，所有输入的 VLAN 资源，都用二元组的区间形式来表示：

删除某一元素后区间的变化

在确定了用二元组表示区间之后，假设要删除某个区间中的某一个数，需要做出如下的 分类讨论：

1. 区间 `(start, end)` 只包含单个数字（即 start == end 成立），而删除的数字 num 就是区间中唯一的数字（即 num == start == end），那么这个区间直接不存在。 例如：删除区间 (5, 5) 中的数字 5，这个区间直接不存在了。

2. 区间 `(start, end)` 包含不止单个数字（即 start < end 成立），而删除的数字 num 是区间的 左端点（即 num == start 成立），那么删除后的新区间是 (start+1, end)。 例如：删除区间 (8, 15) 中的数字 8，新区间为 (9, 15)。

3. 区间 `(start, end)` 包含不止单个数字（即 start < end 成立），而删除的数字 num 是区间的 右端点（即 num == end 成立），那么删除后的新区间是 (start, end-1)。 例如：删除区间 (8, 15) 中的数字 15，新区间为 (8, 14)。

4. 区间 `(start, end)` 包含不止单个数字（即 start < end 成立），而删除的数字 num 既非左端点也非右端点（即 start < num < end 成立），那么删除后这个单个区间会变成 两个新的区间，分别是 (start, num-1) 和 (num+1, end)。 例如：删除区间 (8, 15) 中的数字 11，新区间为 (8, 10) 和 (12, 15)。

因此，上述关于删除的分类讨论可以将其加入到储存区间的过程中，对应代码如下：

将二元组形式转换回原形式

由于储存 vlan_lst 这个过程中的每一个区间都是无序的，输入之前还需要对 vlan_lst 进行 排序。 最终输出的时候，还需要再将二元组区间，转换回原数据形式。 这可以非常方便地通过 推导式结合三目运算符 来完成：

或者使用 for 循环结合 if 语句 完成：

复杂度分析 设 n 为输入资源池中用逗号分隔出的段数（单个数字或一个区间都算一段）。

• 遍历所有段做分类讨论：每一段只做常数次比较和追加操作，且一段最多被拆成两个新区间，这一步是 O(n)，得到的区间列表长度最多为 n+1。
• 对区间列表按起点排序：这是整段代码的瓶颈，时间为 O(n log n)。
• 最后把二元组区间转回字符串并用逗号连接输出：O(n)。

因此总时间复杂度为 O(n log n)，瓶颈在排序这一步。空间上，vlan_lst 与 ans 各存放最多 n+1 个区间或字符串，空间复杂度为 O(n)。另外由题面可知 VLAN ID 的取值范围是 1 到 4094，段数 n 不会超过这个量级，实际运行开销很小。