按点覆盖细分

Question

我做了搜索并查看了以下链接,但没有帮助.

1. 点覆盖问题
2. 用点戳戳(覆盖)的段 - 任何棘手的测试用例？
3. 需要有效的贪婪来覆盖线段

问题描述:

 You are given a set of segments on a line and your goal is to mark as
 few points on a line as possible so that each segment contains at least
 one marked point

任务.

  Given a set of n segments {[a0,b0],[a1,b1]....[an-1,bn-1]} with integer
  coordinates on a line, find the minimum number 'm' of points such that 
  each segment contains at least one point .That is,  find a set of 
  integers X of the minimum size such that for any segment [ai,bi] there 
  is a point x belongs X such that ai <= x <= bi

输出说明:

  Output the minimum number m of points on the first line and the integer 
coordinates of m points (separated by spaces) on the second line

样本输入 - 我

3
1 3
2 5
3 6

输出 - 我

1  
3

样本输入 - II

4
4 7
1 3
2 5
5 6

产出 - II

2   
3 6 

我不明白这个问题本身.我需要解释,如何解决上述问题,但我不想要代码.示例将非常有用

Answer 1

也许这个问题的表述会更容易理解.你n有人可以容忍不同的温度范围[ai, bi].您希望找到最小数量的房间让他们都满意,即您可以将每个房间设置为特定温度,以便每个人都可以在他/她的温度范围内找到房间.

至于如何解决问题,你说你不想要代码,所以我只是粗略地描述一种方法.想想你有最冷的房间.如果使它升温一度不会导致任何人再也无法容忍那个房间,那么你可能会增加,因为这样只能让更多的人使用那个房间.因此,你应该设定的第一个温度是最冷的人仍然可以容忍的温度.换句话说,它应该是最小的bi.现在这个房间将满足您的人员的一些子集,因此您可以将它们从考虑中删除.然后对剩下的人重复这个过程.

现在,为了有效地实现这一点,你可能不想按字面意思做我上面所说的.我建议bi先按照人们排序,对于i第二个人,尝试使用现有房间来满足他们.如果你不能,尝试创造一个具有最高温度的新的,以满足它们bi.

Answer 2

是的，描述相当模糊，对我来说唯一有意义的是：

1. 你有一些线

2. 线上的线段定义为l,r

   其中第一个参数是距线起点的距离，第二个参数是线段长度。很难区分哪个是哪个，因为这些字母对于此类描述来说并不常见。我的赌注是：

   • l段的长度
   • r线段（起点？）距行起点的距离

   

3. 你想找到最小的点集

   这样每个线段中至少有一个点。这意味着对于 2 个重叠的线段，您只需要一个点......

当然，还有更多选择来解决这个问题，最明显的是使用一些启发式方法进行类型和测试，例如仅针对重叠多次的片段进行类型组合。所以我会以这种方式完成这个任务（使用#2中假设的术语）：

1. 对段进行排序r

2. 将重叠数添加到您的分段集数据中

   所以现在该段将为所有段{ r,l,n }设置。n=0

3. 扫描段是否重叠

   就像是

   for (i=0;i<segments;i++) // loop all segments
    for (j=i+1;j<segments;j++) // loop all latter segments until they are still overlapped
     if ( segment[i] and segment [j] are overlapped )
      {
      segment[i].n++; // update overlap counters
      segment[j].n++;
      }
     else break;
   

   现在，如果 r 排序的段重叠，则

   segment[i].r             <=segment[j].r
   segment[i].r+segment[i].l>=segment[j].r
   

4. 处理非重叠段的扫描段

   对于每个线段，segment[i].n==0添加到解点列表的点（中间）由距线起点的距离定义。

   points.add(segment[i].r+0.5*segment[i].l);
   

   然后从列表中删除段（或将其标记为已使用或您为提高速度所做的任何事情......）。

5. 扫描仅重叠一次的段

   因此，如果segment[i].n==1那么您需要确定它是否与i-1or重叠i+1。因此，将重叠的中点添加到解点中，并i从列表中删除线段。然后递减n重叠段的 (i+1或i-1)`，如果为零，也将其删除。

   points.add(0.5*( segment[j].r + min(segment[i].r+segment[i].l , segment[j].r+segment[j].l )));
   

   循环整个扫描，直到没有新的点添加到解决方案中。

6. 现在只剩下多个重叠部分了

   从这一点来看，我会有点含糊，原因有两个：

   1. 我没有测试过这个，也没有任何测试数据来验证，更不用说我很懒了。
   2. 这听起来像是作业，所以你还有一些工作/乐趣。

   从一开始，我就会扫描所有片段并删除所有从内部解决方案中获得任何点的片段。您应该在解决方案发生任何更改后执行此步骤。

   现在，您可以尝试为每个重叠的线段组生成点组合，并记住覆盖组中所有线段的最少点数。（简单地通过暴力）。

   还有更多可能的启发式方法，例如处理所有两次重叠的段（以与单次重叠类似的方式），但最终您将不得不对其余数据进行强力处理......

[edit1] 当您添加新信息时

表示r,l从行首开始左右的距离。所以如果你想在其他公式之间进行转换{ r',l' }然后(l<=r)

l=r`
r=r`+l`

然后回来

r`=l
l`=r-l`

抱歉懒得重写整个事情......