腾讯9-17笔试2

第二题：覆盖数轴
链接：https://www.nowcoder.com/questionTerminal/b95092d4a288475c9f2a0163283e1c8b
来源：牛客网
有一个长度为m的数轴，现在有n个区间，每个区间有一个左右端点，现在需要选择最少的区间，覆盖整个数轴。

输入描述:

第一行两个整数n和m。
接下来n行，每行两个整数，表示区间。

输出描述:

输出最少的区间个数，覆盖整个数轴。如果无法覆盖，输出-1。
n，m不超过100000，区间端点的范围[1,m]。

附上代码，在牛客上提交未通过0.0%，自测用例通过，可能是有问题吧

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int L = in.nextInt();
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
        }
        in.close();
        //group by x,y
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0]) {
                    return -1;
                } else if (o1[0] == o2[0]) {
                    if (o1[1] < o2[1]) {
                        return -1;
                    } else if (o1[1] == o2[1]) {
                        return 0;
                    } else {
                        return 1;
                    }
                } else {
                    return 1;
                }
            }
        });
//        for(int i =0;i<N;i++) {
//            System.out.println(arr[i][0]+" "+arr[i][1]);
//        }
        if(arr[N-1][1]<L||arr[0][0]>1) {
            System.out.println(-1);
        }
        int right = 1;
        int count = 0;
        for (int i = 0; i < N;) {
            int j = 1;
            int pos = j;
            int max = right;
            if(arr[i+j][0]>right) {//判断是否出现断层
                count=-1;
                break;
            }
            while ((i + j) < N && arr[i + j][0] <= right) {//找到能衔接上的能覆盖最右的区间                
                if (arr[i + j][1] > max) {
                    max = arr[i + j][1];
                    pos = j;
                }
                j++;
            }
            right = max;
            i = i + pos;
            count++;
            if(right>=L) break;//覆盖了终点提前结束
        }
        System.out.println(count);
    }

}