1.思路

这题可以用贪心算法做。先按左端点排序，然后更新右端点。不难发现这有三种情况，如图：

第一种情况：①的右端点小于当前区间的右端点

第二种情况：②的右端点大于当前区间的右端点，且②的左端点小于当前区间的右端点

第三种情况：③的左端点和右端点都比当前区间的右端点大

综上，我们可以发现：

如果当前区间右端点大于要比较的区间的左端点，那么这两个区间就可以合并，并且合并之后的右端点为这两个区间右端点的较大值；

如果当前区间右端点小于要比较的区间的左端点，那么这两个区间就不可以合并，答案加1(本题是要统计合并区间的个数)，并且开始统计下一个区间，右端点为下一个区间的右端点。

上面是这题的思路，接下来我来分析一下java如何做这题。首先，我们得用一个数组a来保存区间左右端点，二维数组没有排序方法，如果我们直接要排序就只能自己写，太浪费时间，而且有可能还写不对。所以我们把数组加入list集合，这样就可以重写list集合的sort里面的compare方法，我这里用的是jdk8的新特性做的，很简单。这里的难点就是用到了java不经常用的比较器，对于小白还是很麻烦的。

2.代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a;
        List<int[]> list = new ArrayList<>();   //保存所有区间
        for(int i = 0; i < n; i++) {
            a = new int[2]; //一定要new，如果在外面new的话list保存的还是同一个对象，因为地址相同
            a[0] = in.nextInt();
            a[1] = in.nextInt();
            list.add(a);
        }
        list.sort((o1, o2) -> o1[0] - o2[0]);   //自定义排序，使得区间按左端点升序排列，用的jdk8新特性，不会的自行百度
        int ans = 0;
        int r = Integer.MIN_VALUE;
        for(int[] t : list) {   //遍历区间
            if(t[0] > r)    //如果当前区间左端点大于之前区间的右端点，就代表两个区间不能合并，情况③
                ans++;
            r = Math.max(r, t[1]);  //更新右区间
        }
        System.out.println(ans);
    }
}

3.复杂度分析

• 时间复杂度：O(nlogn),更新区间为O(n),但是之前排序要nlogn
• 空间复杂度：O(n)