题目描述

给定 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

思路

1.将每个区间左端点排序

2.如果下一个区间左端点大于老区间右端点，则找到了新区间，数量+1,
不管有没有找到新区间，每次都更新较长的右端点

ps：单纯计数只需维护右端点

Java 代码

import java.util.*;

public class Main{
    private static int N = 100010;
    private static int[] a;
    private static ArrayList<int[]> list = new ArrayList();
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0;i < n;i++){
            a = new int[2];
            a[0] = scanner.nextInt();
            a[1] = scanner.nextInt();
            list.add(a);
        }
        //对列表中每个数组0位置元素升序排序
        list.sort(new Comparator<int[]>(){
            @Override
            public int compare(int[] o1,int[] o2){
                return o1[0] - o2[0];
            }
        });
        int k = 0;
        int r = Integer.MIN_VALUE;
        for(int a[] : list){
            //下一个区间左端点大于老区间右端点
            if(a[0] > r){
                k++;
            }
            //更新右端点
            r = Math.max(r,a[1]);
        }

        System.out.println(k);
    }
}

上面代码只是单纯计数，如果需要将每个合并区间添加到一个新列表中，如下方法

public static int merge(ArrayList<int[]> list){
        ArrayList<int[]> res = new ArrayList<>();
        list.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int l = Integer.MIN_VALUE;
        int r = Integer.MIN_VALUE;
        for (int[] a : list) {
            //下一个区间左端点大于老区间右端点
            if (a[0] > r){
                //找到了新区间，就将老区间添加(不直接加新区间，因为新区间右端点还没确定)
                if (l != Integer.MIN_VALUE){
                    res.add(new int[]{l,r});
                }
                l = a[0];
                r = a[1];
            }else {
                r = Math.max(r, a[1]);
            }
        }
        //最后一个合并区间,判断条件防止list为空
        if (l != Integer.MIN_VALUE){
            res.add(new int[]{l,r});
        }
        return res.size();
    }