【排序, 双指针】区间合并

题目

803. 区间合并

---

给定 $n$ 个区间 $[l_i, r_i]$，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：$[1,3]$ 和 $[2,6]$ 可以合并为一个区间 $[1,6]$。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含两个整数 $l$ 和 $r$。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

$1 \le n \le 100000$,
$-10^9 \le l_i \le r_i \le 10^9$

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

解题

方法一：排序 双指针

思路

首先把所有区间按左端点升序排序，使用双指针(st、ed)维护一个当前区间，初始化为无穷小(NEG_INF)，然后正向遍历区间数组，此时区间 $[st, ed]$ 与区间 $[seg[0], seg[1]]$ 之间的关系分为两种情况：

1. 区间相交，$ed \ge seg[0]$，此时区间可以合并，区间的右端点变为 $max(ed, seg[1])$。
2. 区间不相交，$ed < seg[0]$，此时区间不能合并，把当前区间加入结果数组(res)并把当前遍历到的区间置为当前区间。

遍历完成后别忘了把最后一个区间加入结果数组（如果区间合法的话）。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int NEG_INF = (int) -2e9;
    static List<int[]> segs = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            int l = (int) in.nval;
            in.nextToken();
            int r = (int) in.nval;
            segs.add(new int[]{l, r});
        }
        System.out.println(merge(segs).size());
    }
    
    static List<int[]> merge(List<int[]> segs) {
        segs.sort((a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        int st = NEG_INF, ed = NEG_INF;
        for (int[] seg : segs) {
            if (ed < seg[0]) {
                if (st != NEG_INF) res.add(new int[]{st, ed});
                st = seg[0];
                ed = seg[1];
            } else ed = Math.max(ed, seg[1]);
        }
        if (st != NEG_INF) res.add(new int[]{st, ed});
        return res;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> intervals;

int main () {
    scanf("%d", &n);
    while (n-- > 0) {
        int l, r;
        scanf("%d%d", &l, &r);
        intervals.push_back({l, r});
    }
    sort(intervals.begin(), intervals.end(), [] (auto& a, auto& b) {
        return a.first < b.first;
    });
    int cnt = 0;
    int st = -2e9, ed = -2e9;
    for (auto& interval : intervals) {
        if (ed < interval.first) {
            if (st != -2e9) ++cnt;
            st = interval.first, ed = interval.second;
        } else ed = max(ed, interval.second);
    }
    if (st != -2e9) ++cnt;
    printf("%d\n", cnt);
    
    return 0;
}