如何定义覆盖所有大厦的最小摄像机数量？ [英] How do I define the minimum number of cameras to cover all the edifice?
问题描述
大家好。我需要在java中解决这个问题的方法。
我们是一家安全公司，我们必须监控一幢建筑物。大厦具有正多边形的形状，并且根据我们拥有的摄像机的数量和这些摄像机的行为，该程序必须扣除覆盖多边形的所有墙壁的最小数量的摄像机。
每个摄像机都包含两个整数ai和bi，用于定义覆盖的墙壁数量。
-if ai<然后，相机覆盖自墙壁ai直到墙壁bi，即（ai <= j <= bi），j =墙壁覆盖。
-if ai>然后摄像机盖住自墙壁ai直到墙壁n，或从墙壁1覆盖直到墙壁bi;即（ai< = j< = n），或（1 <= j< = bi）; j =墙壁覆盖。
输入参数是：
-n：墙壁数量，和（3 <= n< = 10 ^ 6）。
-k：摄像机数量，和（1 <= k <= 10 ^ 6）
- 每个摄像机的ai，bi，和（1< =&& bi< = n）
流程：
。
。
。
输出参数为：
-minimun摄像机数量。 />
示例1：
输入：
8 2
8 4
5 8
输出：
2
示例2：
输入：
100 7
1 50
50 70
70 100
90 40
20 60
60 80
80 20
输出：
3
PD：对不起我的英语
我尝试了什么：
我试图用一种形式来思考正确的过程，但是我需要一个主意或者接近。
Hello people. I need a approach for this problem in java.
We are a security company and we have to monitor a building. The edifice has the form of a regular polygon, and depending on the number of cameras that we have and the behavior of these cameras, this program has to deduct the minimum number of cameras to cover all the walls of the polygon.
Each of the cameras contains two integers ai and bi that defines the number of walls that cover.
-if ai < bi then the camera covers since the wall ai until the wall bi, that is (ai <= j <= bi), j = walls covers.
-if ai > bi then the camera covers since the wall ai until the wall n, or covers since the wall 1 until the wall bi; that is (ai <= j <= n), or (1 <= j <=bi); j = walls covers.
The input parameters are:
-n: number of walls, and (3 <= n<= 10^6).
-k: number of cameras, and (1 <= k <= 10^6)
- ai, bi for each camera, and (1 <= ai && bi <= n)
The process:
.
.
.
The output parameters are:
-minimun number of cameras.
Example 1:
input:
8 2
8 4
5 8
output:
2
Example 2:
input:
100 7
1 50
50 70
70 100
90 40
20 60
60 80
80 20
output:
3
PD: sorry for my english
What I have tried:
I tried to think in a form for solve the process correctly, but I need an idea or approach.
推荐答案
你需要首先找出问题的逻辑，并创建一个算法来找到答案。但这是你的工作，我们不是来做你的功课。
You need to figure out the logic of the question first, and create an algorithm to find the answer. But that is your job, we are not here to do your homework.
这篇关于如何定义覆盖所有大厦的最小摄像机数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
