找到重叠间隔的最小的子集 [英] Find the smallest subset of overlapping intervals

问题描述

考虑一个问题，找到一个最小支配集间隔图形。在间隔调度的情况下，它被转换为下面的问题：

有多个间隔可被或相互重叠。 发现间隔的最小的子集，使得对于未包含在所述子集中的每个间隔，就会发现至少1间隔的子集，将与它重叠。

有一个约定贪婪的解决方案可从互联网上的不同来源，康奈尔等为一体的解决方案： http://www.cs.cornell.edu/Courses/cs4820 /2011sp/handouts/samplesolutions.pdf

  

我们的工作，以填补了一组C的组成委员会（集   间隔）。我们用一个集合M持有'覆盖'间隔   记账。

     

  
1. 排序间隔由完成时间与最早完成时间第一。
  
2. 乘坐区间i的S采用最早完成时间。
  
3. 在构建集O = {S∈s ^ | S相交我}
  
4. 以Ø∈O，其最迟完成时间，并添加Ø到C，加入所有与相交0至M的间隔
  
5. 在重复2-4，直到所有的时间间隔都包括在内。
  

这是类似于在SO在2012年提供的interjay一个投了答案： 找到最小的一组重叠的工作

不过，我注意到一个反例，证明上述方案不会产生最低的子集：

考虑间隔：[0,2]，[1,4]，[3,10]，[5,6]，[7,8]，[9,10]

一个最小子集应具有2间隔：[3，10]加上任一[0,2]或[1,4]

但是，上述解决方案将返回的4个间隔的一个子集：[1,4]，[5,6]，[7,8]和[9,10]。最长的区间[3,10]是prematurely拒绝在第4步。

有没有比那些上面贴一个更好的贪婪的解决方案？谢谢！

解决方案

你所引用的算法不正确，因为集合S永远不会改变，所以在第2步相同的时间间隔总是会挑，你会进入一个无限循环。如果更改步骤2，就拿我的时间间隔在SM与最早完成时间，这将是正确的。

您链接

我的回答是正确不过。它和上面的修正算法将给集合{[1,4]，[3,10]}为你的榜样。

您正在做的可能是，在上述步骤3（或在我的链接回答步骤2）你正在寻找只在集这是在SM的错误（称为A在我的答案）。但是，你应该看看相交我所有的时间间隔，即使他们已经在并购。

Consider a question to find a minimum dominating set of an interval graph. In the context of interval scheduling, it is converted to the question below:

There are multiple intervals which may or may overlap with each other. Find a minimum subset of the intervals, so that for every interval that is not included in the subset, it will find at least 1 interval in the subset that will overlap with it.

There is an agreed greedy solution available from various sources on the Internet, such as one solution from Cornell: http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/samplesolutions.pdf

We work to fill up a set C which makes up the committee (subset of intervals). We use a set M to hold ’covered’ intervals for bookkeeping.

1. Sort the intervals by finish time with earliest finish time first.
2. Take the interval i in S with earliest finish time.
3. Construct set O = {s ∈ S|s intersects i}
4. Take o ∈ O with the latest finish time and add o to C, add all the intervals that intersect with o to M
5. repeat 2-4 until all intervals are covered.

This is similar to a voted up answer provided by interjay in 2012 on SO: Find the smallest set of overlapping jobs

But I have noticed a counterexample that proves the above solution does not produce the minimum subset:

Consider intervals: [0,2], [1,4], [3,10], [5, 6], [7,8], [9, 10].

A minimum subset should have 2 intervals: [3, 10] plus either [0, 2] or [1, 4].

But the above solution will return a subset of 4 intervals: [1,4], [5,6], [7,8] and [9,10]. The longest interval [3,10] was prematurely rejected at step 4.

Is there a better greedy solution than the ones posted above? Thanks!

解决方案

The algorithm you quoted is incorrect because the set S never changes, so in step 2 the same interval will always be picked and you will enter an infinite loop. If you change step 2 to "Take the interval i in S-M with earliest finish time.", it will be correct.

My answer which you linked is correct however. Both it and the corrected algorithm above will give the set {[1,4], [3,10]} for your example.

The mistake you're making may be that in step 3 above (or step 2 in my linked answer) you're looking only at sets which are in S-M (called A in my answer). But you should look at all intervals that intersect i, even if they are already in M.

这篇关于找到重叠间隔的最小的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！