题目链接
题目描述
一个系统根据操作日志来启用或禁用多种算法。操作日志包含两种记录：“启用 (algorithm)” 和 “禁用 (undo algorithm)” 一系列指定范围内的算法ID。任务是处理完所有日志后，输出最终处于“启用”状态的所有算法ID，并将其合并为最简的、无重叠的、升序排列的区间集合。
解题思路
本题的核心是处理区间的合并与移除，是一个经典的区间管理问题。我们可以维护一个列表，用于存储当前所有处于“启用”状态的、无重叠且已排序的区间。
算法步骤如下：
-
数据结构：
- 使用一个列表（如 C++ 的
vector<pair<int, int>>或 Python 的list of lists）来存储启用的区间[start, end]。始终保持这个列表中的区间是按起始点排序的，并且互相之间不重叠。
- 使用一个列表（如 C++ 的
-
区间解析：
- 首先，需要一个辅助函数来解析输入的范围字符串（如
"1-10,15,20-25"）。该函数应将字符串分割，并转换成一个区间列表[[1, 10], [15, 15], [20, 25]]。
- 首先，需要一个辅助函数来解析输入的范围字符串（如
-
处理操作：
-
启用 (
algorithm) 操作:- 将新解析出的所有待启用区间与主列表中的现有启用区间合并。
- 对合并后的列表进行排序（按区间起点）。
- 遍历排序后的列表，将所有重叠或相邻的区间进行合并，生成一个新的、无重叠的区间列表。例如，
[1, 5]和[4, 8]会合并成[1, 8]；[1, 5]和[6, 8]会合并成[1, 8]。 - 用这个新的无重叠列表替换旧的主列表。
-
禁用 (
undo algorithm) 操作:- 解析出待禁用的区间。
- 对于每一个待禁用的区间
d = [d_start, d_end]，遍历当前所有已启用的区间e = [e_start, e_e_end]。 d和e的关系有以下几种：- 无交集：
e不受影响。 d完全覆盖e：e被完全禁用，从列表中移除。d裁剪e的头部：e变为[d_end + 1, e_end]。d裁剪e的尾部：e变为[e_start, d_start - 1]。d从中间将e分裂：e分裂成两个新的小区间[e_start, d_start - 1]和[d_end + 1, e_end]。
- 无交集：
- 每次禁用操作后，都会生成一个新的启用区间列表，用它来更新主列表。
-
-
格式化输出：
- 所有操作处理完毕后，遍历最终的启用区间列表。
- 将每个区间
[start, end]格式化为字符串：如果start == end，格式化为"start"；否则，格式化为"start-end"。 - 用逗号
","连接所有格式化后的字符串并输出。
这个方法虽然在每次操作后都可能需要遍历整个区间列表，但逻辑清晰，易于实现。
代码
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
using Interval = pair<int, int>;
// 解析范围字符串，例如 "1-10,15"
vector<Interval> parse_ranges(const string& s) {
vector<Interval> ranges;
stringstream ss(s);
string segment;
while (getline(ss, segment, ',')) {
size_t dash_pos = segment.find('-');
if (dash_pos != string::npos) {
int start = stoi(segment.substr(0, dash_pos));
int end = stoi(segment.substr(dash_pos + 1));
ranges.push_back({start, end});
} else {
int val = stoi(segment);
ranges.push_back({val, val});
}
}
return ranges;
}
// 合并重叠区间
void merge_intervals(vector<Interval>& intervals) {
if (intervals.empty()) {
return;
}
sort(intervals.begin(), intervals.end());
vector<Interval> merged;
merged.push_back(intervals[0]);
for (size_t i = 1; i < intervals.size(); ++i) {
if (intervals[i].first <= merged.back().second + 1) {
merged.back().second = max(merged.back().second, intervals[i].second);
} else {
merged.push_back(intervals[i]);
}
}
intervals = merged;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
string line;
getline(cin, line); // 消耗掉第一行末尾的换行符
vector<Interval> enabled_intervals;
for (int i = 0; i < n; ++i) {
getline(cin, line);
stringstream ss(line);
string type, keyword, ranges_str;
ss >> type;
if (type == "undo") { // 禁用操作
ss >> keyword >> ranges_str; // keyword 是 "algorithm"
} else { // 启用操作
ss >> ranges_str;
}
vector<Interval> current_ranges = parse_ranges(ranges_str);
if (type == "algorithm") {
enabled_intervals.insert(enabled_intervals.end(), current_ranges.begin(), current_ranges.end());
merge_intervals(enabled_intervals);
} else { // 禁用
vector<Interval> next_enabled;
for (const auto& enabled : enabled_intervals) {
vector<Interval> pieces;
pieces.push_back(enabled);
for (const auto& to_undo : current_ranges) {
vector<Interval> new_pieces;
for (const auto& p : pieces) {
// 没有交集
if (p.second < to_undo.first || p.first > to_undo.second) {
new_pieces.push_back(p);
continue;
}
// 保留左侧部分
if (p.first < to_undo.first) {
new_pieces.push_back({p.first, to_undo.first - 1});
}
// 保留右侧部分
if (p.second > to_undo.second) {
new_pieces.push_back({to_undo.second + 1, p.second});
}
}
pieces = new_pieces;
}
next_enabled.insert(next_enabled.end(), pieces.begin(), pieces.end());
}
enabled_intervals = next_enabled;
merge_intervals(enabled_intervals);
}
}
if (!enabled_intervals.empty()) {
for (size_t j = 0; j < enabled_intervals.size(); ++j) {
if (enabled_intervals[j].first == enabled_intervals[j].second) {
cout << enabled_intervals[j].first;
} else {
cout << enabled_intervals[j].first << "-" << enabled_intervals[j].second;
}
if (j < enabled_intervals.size() - 1) {
cout << ",";
}
}
cout << "\n";
}
return 0;
}
import java.util.*;
class Interval {
int start;
int end;
Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public class Main {
// 解析范围字符串
private static List<Interval> parseRanges(String s) {
List<Interval> ranges = new ArrayList<>();
String[] segments = s.split(",");
for (String segment : segments) {
if (segment.contains("-")) {
String[] parts = segment.split("-");
ranges.add(new Interval(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])));
} else {
int val = Integer.parseInt(segment);
ranges.add(new Interval(val, val));
}
}
return ranges;
}
// 合并重叠区间
private static List<Interval> mergeIntervals(List<Interval> intervals) {
if (intervals.isEmpty()) {
return new ArrayList<>();
}
intervals.sort(Comparator.comparingInt(a -> a.start));
LinkedList<Interval> merged = new LinkedList<>();
for (Interval interval : intervals) {
if (merged.isEmpty() || merged.getLast().end + 1 < interval.start) {
merged.add(new Interval(interval.start, interval.end));
} else {
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}
return new ArrayList<>(merged);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
List<Interval> enabledIntervals = new ArrayList<>();
for (int i = 0; i < n; i++) {
String line = sc.nextLine();
String[] parts = line.split(" ");
String type = parts[0];
String rangesStr;
if (type.equals("undo")) {
rangesStr = parts[2];
} else { // "algorithm"
type = "algorithm";
rangesStr = parts[1];
}
List<Interval> currentRanges = parseRanges(rangesStr);
if (type.equals("algorithm")) {
enabledIntervals.addAll(currentRanges);
enabledIntervals = mergeIntervals(enabledIntervals);
} else { // undo
List<Interval> nextEnabled = new ArrayList<>();
for (Interval enabled : enabledIntervals) {
List<Interval> temp = new ArrayList<>();
temp.add(enabled);
for (Interval toUndo : currentRanges) {
List<Interval> afterUndo = new ArrayList<>();
for (Interval current : temp) {
// No overlap
if (current.end < toUndo.start || current.start > toUndo.end) {
afterUndo.add(current);
continue;
}
// Left part remains
if (current.start < toUndo.start) {
afterUndo.add(new Interval(current.start, toUndo.start - 1));
}
// Right part remains
if (current.end > toUndo.end) {
afterUndo.add(new Interval(toUndo.end + 1, current.end));
}
}
temp = afterUndo;
}
nextEnabled.addAll(temp);
}
enabledIntervals = mergeIntervals(nextEnabled);
}
}
if (!enabledIntervals.isEmpty()) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < enabledIntervals.size(); j++) {
Interval interval = enabledIntervals.get(j);
if (interval.start == interval.end) {
sb.append(interval.start);
} else {
sb.append(interval.start).append("-").append(interval.end);
}
if (j < enabledIntervals.size() - 1) {
sb.append(",");
}
}
System.out.println(sb.toString());
}
}
}
import sys
def parse_ranges(s):
# 解析范围字符串为区间列表
ranges = []
for part in s.split(','):
if '-' in part:
start, end = map(int, part.split('-'))
ranges.append([start, end])
else:
val = int(part)
ranges.append([val, val])
return ranges
def merge_intervals(intervals):
"""合并重叠或相邻的区间"""
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for i in range(1, len(intervals)):
current_start, current_end = intervals[i]
last_start, last_end = merged[-1]
if current_start <= last_end + 1:
merged[-1][1] = max(last_end, current_end)
else:
merged.append([current_start, current_end])
return merged
def main():
n = int(input())
enabled_intervals = []
for _ in range(n):
parts = input().strip().split()
op_type = parts[0]
if op_type == "undo":
ranges_str = parts[2]
else: # "algorithm"
op_type = "algorithm"
ranges_str = parts[1]
current_ranges = parse_ranges(ranges_str)
if op_type == "algorithm":
enabled_intervals.extend(current_ranges)
enabled_intervals = merge_intervals(enabled_intervals)
else: # "undo"
next_enabled = []
for enabled in enabled_intervals:
temp_intervals = [enabled]
for to_undo in current_ranges:
after_undo_temp = []
for temp_interval in temp_intervals:
e_start, e_end = temp_interval
u_start, u_end = to_undo
# 保留非重叠的左边部分
if e_start < u_start:
after_undo_temp.append([e_start, min(e_end, u_start - 1)])
# 保留非重叠的右边部分
if e_end > u_end:
after_undo_temp.append([max(e_start, u_end + 1), e_end])
temp_intervals = after_undo_temp
next_enabled.extend(temp_intervals)
enabled_intervals = merge_intervals(next_enabled)
if enabled_intervals:
result = []
for start, end in enabled_intervals:
if start == end:
result.append(str(start))
else:
result.append(f"{start}-{end}")
print(",".join(result))
if __name__ == "__main__":
main()
算法及复杂度
- 算法：区间操作（合并、移除）
- 时间复杂度：设
为操作总数，
为当前已启用区间的数量，
为单次操作指令中的子区间数量。
- 启用 (
algorithm) 操作的复杂度主要在于排序和合并，约为。
- 禁用 (
undo) 操作是性能瓶颈。每个已启用区间都可能被个新区间。对这些新区间进行合并的成本（主要是排序）为
。
- 因此，单次操作的最坏时间复杂度由禁用操作决定。
- 启用 (
- 空间复杂度：
，其中
是执行过程中出现过的最大不相交区间数，用于存储这些区间。
京公网安备 11010502036488号