首页 > 试题广场 >

视野争夺

[编程题]视野争夺

小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

输入

算法知识视频讲解

小牛冲冲冲jiang

发表于 2021-09-25 19:31:25

import java.util.Scanner; import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) { Scanner sc 展开全文

英雄草帽

发表于 2022-05-07 19:54:31

import java.util.*; public class Main{ public static void main(String[] args) { Scanner 展开全文

大厂算法岗必拿下

发表于 2021-09-23 08:25:31

这是一个线段性质的问题。注意如何从左边到右边，依次处理了基本的三个线段关系，以及i达到最后一个的时候怎么判断是否能覆盖。（很重要） #include<bits/stdc++.h> using namespace std; int main(){ int n; long 展开全文

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师腾讯 2020 Java工程师

上传者：小小

难度：

35条回答 225收藏 13864浏览

视野争夺

扫一扫，把题目装进口袋