本題的鏈接是：視野爭奪

題目描述

小Q在進(jìn)行一場競技游戲,這場游戲的勝負(fù)關(guān)鍵就在于能否能爭奪一條長度為L的河道,即可以看作是[0,L]的一條數(shù)軸。
這款競技游戲當(dāng)中有n個(gè)可以提供視野的道具?真視守衛(wèi),第i個(gè)真視守衛(wèi)能夠覆蓋區(qū)間[xi,yi]。現(xiàn)在小Q想知道至少用幾個(gè)真視守衛(wèi)就可以覆蓋整段河道。

輸入描述:

輸入包括n+1行午绳。

第一行包括兩個(gè)正整數(shù)n和L

接下來的n行,每行兩個(gè)正整數(shù)袜硫，表示第i個(gè)覆蓋的區(qū)間

輸出描述

一個(gè)整數(shù)，表示最少需要的真視守衛(wèi)數(shù)量, 如果無解, 輸出-1吟孙。

輸入例子1:

4 6
3 6
2 4
0 2
4 7

輸出例子1:

3

解題思路-貪心算法

先把數(shù)組按照起始節(jié)點(diǎn)升序讨阻，按照結(jié)束節(jié)點(diǎn)降序芥永，我們利用貪心的思想：每一次選擇下一個(gè)節(jié)點(diǎn)它的起始節(jié)點(diǎn)都是在前一個(gè)節(jié)點(diǎn)范圍內(nèi)，結(jié)束節(jié)點(diǎn)越大越好

代碼

   package niuke.tencent;

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

public class shiyezhengduo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int l = scanner.nextInt();
        int [][]nums = new int[n][2];
        int index = 0;
        int result = 1;
        int end = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<2;j++){
                nums[i][j] = scanner.nextInt();
            }
        }
//        兩個(gè)維度第一個(gè)增序钝吮，第二個(gè)降序
        Arrays.sort(nums, new Comparator<int[]>() {
            public int compare(int[] a, int[] b){
                if(a[0]==b[0]){
                    return b[1] - a[1];
                }else {
                    return a[0] - b[0];
                }
            }
        });
        end = nums[index][1];
        while(index<nums.length && end < l){
            int local = index;
            int max = -1;
            int max_value = nums[local][1];
            for(int i=index+1;i<nums.length&&nums[i][0]>=nums[local][0]&&nums[i][0]<=nums[local][1];i++){
                if(nums[i][1] > max_value){
                    max_value = nums[i][1];
                    max = i;
                }
            }
            if(max == -1){
                break;
            }
            index = max;
            end = nums[index][1];
            result++;
        }
        if(end>=l)
            System.out.println(result);
        else
            System.out.println(-1);

    }
}