腾讯8.17 技术笔试第三题有AC大佬吗,求解救

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

输入描述
输入包括n+1行
第一行包括两个正整数n和L(1<=n<=10^5,1<=L<=10^9)
接下来的n行,每行两个正整数xi,yi(0<=xi<=yi<=10^9),表示第i个真视守卫覆盖的区间

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

样例:
输入:
4 6
3 6
2 4
0 2
4 7
输出
3

#腾讯##笔试题目#
全部评论
public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); int L=input.nextInt(); int[][] nums=new int[n][2]; int ce=0; while(ce<n) { nums[ce][0]=input.nextInt(); nums[ce][1]=input.nextInt(); ce++; } System.out.println(guidenum(nums,L)); } public static int guidenum(int[][] nums,int L) { int count=0; Arrays.sort(nums,(a,b)->a[0]-b[0]); int start=0,end=0; for(int i=0;start<L;) { for(;i<nums.length&&nums[i][0]<=start;i++) end=Math.max(end,nums[i][1]); if(start==end)return -1; start=end; count++; } return count; }
点赞 回复
分享
发布于 2019-08-18 17:18
区间覆盖问题,先排序所有区间,再贪心来做。 import java.util.Arrays; import java.util.Scanner; public class E3 {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         while(in.hasNext()) {             int n = in.nextInt();             int l = in.nextInt();             int[][] interval = new int[n][2];             for(int i = 0; i < n; ++i) {                 interval[i][0] = in.nextInt();                 interval[i][1] = in.nextInt();             }             Arrays.sort(interval, (a, b) -> {return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];});             boolean able = true;             int i = 0, k = 0;             int max = 0; //最右能到的位置             int start = 0; //起始位置             int cnt = 0;//区间数             while(start < l) {                 if(interval[k][0] > start) {                     able = false;                     break;                 }                 for(i = k; i < n; ++i) {                     if(interval[i][0] <= start) {                         max = Math.max(interval[i][1], max);                     } else {                         ++cnt;                         start =  max;                         k = i;                         break;                     }                 }                 if(i == n) {                     ++cnt;                     break;                 }             }             if(able) {                 System.out.println(cnt);             } else {                 System.out.println(-1);             }         }     } }
点赞 回复
分享
发布于 2019-08-18 17:18
秋招专场
校招火热招聘中
官网直投

相关推荐

点赞 8 评论
分享
牛客网
牛客企业服务