时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。
这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[x,y]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。

输入描述:

输入包括n+1行。

第一行包括两个正整数n和L(1<=n<=10> ,1<=L<=10> )
接下来的n行,每行两个正整数x> ,y> (0<=x> <=y> <=10> ),表示第i个真视守卫覆盖的区间。

输出描述:

一个整数，表示最少需要的真视守卫数量, 如果无解, 输出-1。

输入例子1:

4 6 3 6 2 4 0 2 4 7

输出例子1:

3

暴力贪心

import java.util.Scanner;
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int L = sc.nextInt();
        int[][] xy = new int[2][n];
        for (int i = 0; i < n; i++) {
            xy[0][i] = sc.nextInt();
            xy[1][i] = sc.nextInt();
        }
        sc.close();
        int ans = 0;
        int f = 0;
        while (f <= L) {
            if (func(xy, f) > f) {
                f = func(xy, f);
            } else {
                System.out.println(-1);
            }
            ans++;
            if (f >= L) {
                System.out.println(ans);
            }
        }
    }
    public static int func(int[][] xy, int f) {
        // x[0][i] < f, max(x[1][i]>f)
        int ans = f;
        for (int i = 0; i < xy[0].length; i++) {
            if (xy[0][i] <= f && xy[1][i] > ans) {
                ans = xy[1][i];
            }
        }
        return ans;
    }
}

贪心-优化

先进行排序、贪心

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int L = sc.nextInt();
        int[][] xy = new int[n][2];
        for (int i = 0; i < n; i++) {
            xy[i][0] = sc.nextInt();
            xy[i][1] = sc.nextInt();
        }
        sc.close();
        Arrays.sort(xy, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
            }
        });
        if (xy[0][0] > 0) {
            System.out.println(-1);
            return;
        }
        // r向右的范围，max 
        int ans = 1, idx = 0, r = xy[0][1], max = 0;
        while (r < L) {
            max = 0;
            boolean f = false;
            while (idx < n && xy[idx][0] <= r) {
                f = true;
                // max 此刻的最右范围
                max = Math.max(max, xy[idx][1]);
                idx++;
            }
            if (!f) {
                System.out.println("-1");
                return;
            }
            r = max;
            ans++;
        }
        System.out.println(ans);
    }
}