本笔记内容来源于算法基础课

区间合并

基本知识

给定$n$个区间，对所有有交集的区间进行合并

注意端点重合也属于交集

思路

1. 所有区间按照左端点进行排序
2. 从左向右扫描，维护一个最长的合并区间

考虑当前维护的区间[st, ed]与第i个区间的关系

1. 内部 [st, ed] -> [st, ed]
2. 交集 [st, ed] -> [st, i.ed]
3. 外部 [st, ed] -> [i.st, i.ed]

观察到2只更新右端点，而3需要更新左右端点

也就是说当新区间的左断点大于当前区间的右断点，则将当前区间加入结果中，维护新区间
否则扩展当前维护的区间ed = Integer.max(ed, i.ed)

最后将维护的区间加入结果集中

模板

注意：

1. 初始区间定义为最左端点之外
2. 在插入结果时要判断是否为初始区间
3. 在扫描完成后，要插入剩下的区间，同时要判断避免为初始区间

// 左端点排序
Collections.sort(regions, (o1, o2) -> o1.st - o2.st);
// 左端点之外
int st = (int)-2e9, ed = (int)-2e9;
for (int i = 0; i < n; i++) {
    if (regions.get(i).st > ed) {
        // 非初始区间则加入
        if (st != (int)-2e9) res.add(new Region(st, ed));
        st = regions.get(i).st;
        ed = regions.get(i).ed;
    } else 
        ed = Integer.max(ed, regions.get(i).ed);
}

// 非初始区间则加入
if (st != (int)-2e9) res.add(new Region(st, ed));