区间合并

区间合并

给定 n 个区间 ，要求合并所有有交集的区间。

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

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

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

方法：

1. 按区间左端点排序
2. 分三种情况讨论

经典例子：

给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。

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

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

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

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含两个整数 ll 和 rr。

输出格式

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

数据范围

1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < n; ++i) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            list.add(new int[]{l, r});
        }
        int res = 0;
        list.sort((a, b) -> a[0] - b[0]);
        int st = (int)-2e9, ed = (int)-2e9;
        for(int i = 0; i < list.size(); ++i) {
            int[] tmp = list.get(i);
            if(ed < tmp[0]) {
                if(ed != -2e9) {
                    res++;
                }
                st = tmp[0];
                ed = tmp[1];
            } else {
                ed = Math.max(ed, tmp[1]);
            }
        }
        if(st != -2e9) res++;
        System.out.print(res);
    }
}