视野争夺

[编程题]视野争夺

热度指数：8276 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。

这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[x_i,y_i]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。

输入描述:

输入包括n+1行。

第一行包括两个正整数n和L(1<=n<=10⁵,1<=L<=10⁹)

接下来的n行,每行两个正整数x_i,y_i(0<=x_i<=y_i<=10⁹),表示第i个真视守卫覆盖的区间。

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Java

NutYY

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[][] temp=new int[n][2];
		for(int i=0;i<n;i++) {
			for(int j=0;j<2;j++) {
				temp[i][j]=in.nextInt();
			}
		}
		//。获得了数组，进行排序
		Arrays.sort(temp,new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
			}
		});
		int index=0;
		int count=0;
		int pre=0;   //右边界
		while(pre<L) {
			if(temp[index][0]>pre) {
				System.out.println(-1);
			}
			int max=0;
			while(index<n&&temp[index][0]<=pre) {
				max=Math.max(max, temp[index][1]);
				index++;
			}
			count++;
			pre=max;
			if(pre>=L) {
				System.out.println(count);
                return;
			}
			if(index>=n) {
				System.out.println(-1);
                return;
			}
		}
	}
}

Java贪心算法

编辑于 2020-04-27 17:09:45 回复(4)