题目描述

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

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

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

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

输入格式
第一行包含整数 n。

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

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

数据范围
1≤n≤100000,
−109≤li≤ri≤109

输入样例

5
1 2
2 4
5 6
7 8
7 9

输出样例

3

算法1

JAVA 代码

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


public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        ArrayList<int[]> res = new ArrayList<>();
        while (num-- > 0){
            String[] res1 = br.readLine().split(" ");
            int[] nums = new int[2];
            nums[0] = Integer.parseInt(res1[0]);
            nums[1] = Integer.parseInt(res1[1]);
            res.add(nums);
        }
        Collections.sort(res,new Comparator<int[]>(){//对数组第一个数字进行升序排序
            public int compare(int[] a, int[] b){
                return a[0] - b[0];  //返回值大于0，则将两个变量交换，如a[1, 2], b[0, 1] 此时a[0] > b[0], 
            }                           //所以他们交换在res中变成b[0, 1],a[1,2]
        });
        ArrayList<int[]> out = new ArrayList<>();
        int st = Integer.MIN_VALUE;
        int ed = Integer.MIN_VALUE;
        for (int i = 0; i < res.size(); i++){
            if (ed < res.get(i)[0]){
                if (st != Integer.MIN_VALUE){
                    out.add(new int[]{st, ed});
                }
                st = res.get(i)[0];
                ed = res.get(i)[1];
            }else {
                ed = Math.max(ed, res.get(i)[1]);
            }
        }
        if (st != Integer.MIN_VALUE){  //最后一个区间的右边界判别了之后进行添加，if是为了防止res为空
            out.add(new int[]{st, ed});
        }
        System.out.print(out.size());
    }
}