编辑代码

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

class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入可选覆盖线段个数：");
        int N = sc.nextInt();
        System.out.print("请输入区间长度：");
        int T = sc.nextInt();
        Job[] jobs = new Job[N];
        for (int i = 0; i < N; i++) {
            jobs[i] = new Job(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(jobs);
        int start = 1;// 要覆盖的目标点，end覆盖该点的所有区间中右端点最右
        int end = 1;
        int ans = 1;
        for (int i = 0; i < N; i++) {

            int s = jobs[i].s;
            int t = jobs[i].t;

            if (i == 0 && s > 1)
                break;

            if (s <= start) {// 当前区间有可能覆盖start
                end = Math.max(t, end);// 更新更右的端点
            } else {// 开始下一个区间
                ans++;// 上一个目标覆盖已经达成，计数加1
                start = end + 1;// 更新起点，设置一个新的覆盖目标
                if (s <= start) {
                    end = Math.max(t, end);
                } else {
                    break;
                }
            }
            if (end >= T) {// 当前的end超越了线段的右侧
                break;
            }

        }
        if (end < T)
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    private static class Job implements Comparable<Job> {
        int s;
        int t;

        public Job(int s, int t) {
            this.s = s;
            this.t = t;
        }

        /** 按照区间起点排序 */
        @Override
        public int compareTo(Job other) {
            int x = this.s - other.s;
            if (x == 0)
                return this.t - other.t;
            else
                return x;
        }
    }
}