假设我有一个区间(a,b),以及一些子区间{(ai,bi)}i,它们的并集是整个(a,b)。是否有一种有效的方法来选择一个最小基数子集,使其仍然覆盖(a,b)?
从a或b开始的贪心算法总是给出最优解。
证明:考虑覆盖a的所有子区间集合Sa,显然,其中一个必须属于最优解。如果我们用Sa中右端点bmax最大(到达最右侧)的子区间(amax,bmax)替换它,剩余的未覆盖区间(bmax,b)将是剩余区间的子集,并且可以用不多于最优解中类似未覆盖区间的子区间进行覆盖。因此,由(amax,bmax)和剩余区间(bmax,b)的最优解构建的解也是最优的。
因此,只需从a开始,迭代选择最右侧的区间(并覆盖前一个区间的末端),重复直到达到b。如果将区间存储在增强区间树中,则我相信可以以log(n)的时间复杂度来选择下一个区间。
听起来像是动态规划。
以下是该算法的示例(假设区间已按结束时间排序并存储在列表中):
//works backwards from the end
int minCard(int current, int must_end_after)
{
if (current < 0)
if (must_end_after == 0)
return 0; //no more intervals needed
else
return infinity; //doesn't cover (a,b)
if (intervals[current].end < must_end_after)
return infinity; //doesn't cover (a,b)
return min( 1 + minCard(current - 1, intervals[current].start),
minCard(current - 1, must_end_after) );
//include current interval or not?
}
但它也应该涉及缓存(记忆化)。
有两种情况需要考虑:
情况1:在一个间隔结束后,没有重叠的间隔。在这种情况下,选择下一个起始时间最小且完成时间最长的间隔(amin,bmax)。
情况2:有1个或多个间隔与您正在查看的最后一个间隔重叠。在这种情况下,起始时间并不重要,因为您已经覆盖了它。 因此,优化完成时间。(a,bmax)。
情况1始终将第一个间隔选择为最佳集合中的第一个间隔(证明与@RafalDowgrid提供的相同)。
你的意思是子间隔仍然重叠,以便(a,b)在所有点上仍然完全被覆盖吗?
也许可以将子间隔本身分成基本块,与它们来自哪里相关联,这样您就可以为每个基本块间隔列出选项,考虑到子间隔还覆盖了其他区域。然后您可以使用基于每个子子间隔的搜索,并确保没有留下任何空隙。
然后需要高效地进行搜索...这会更加困难。
可以消除完全被其他更少数量的一组集合完全覆盖的任何间隔集合,并在预处理之后解决问题。
整体的最小值不是至少有一半的最小值吗?我不确定。