点覆盖问题

我最近在测试中遇到了这个问题：给定一组点m（全部在 x 轴上）和一组n具有端点的线[l, r]（再次在 x 轴上），找到 的最小子集n这样所有的点都被一条线覆盖。证明你的解决方案总是能找到最小子集。

我为它编写的算法的效果是： （假设线存储为数组，左端点位于位置 0，右端点位于位置 1）

algorithm coverPoints(set[] m, set[][] n):
    chosenLines = []
    while m is not empty:
        minX = min(m)
        bestLine = n[0]
        for i=1 to length of n:
            if n[i][0] <= minX and n[i][1] > bestLine[1] then
                bestLine = n[i]
        add bestLine to chosenLines
        for i=0 to length of m:
            if m[i] <= bestLine[1] then delete m[i] from m
    return chosenLines

我只是不确定这是否总能找到最小的解决方案。这是一个简单的贪婪算法，所以我的直觉告诉我它不会，但是我的一位朋友在这方面比我强得多，他说对于这个问题，像这样的贪婪算法总是能找到最小解决方案。为了证明我的总是能找到最小的解决方案，我通过矛盾做了一个非常手工的波浪式证明，其中我做出了一个可能根本不正确的假设。我完全忘记了我做了什么。

如果这不是一个最小的解决方案，有没有办法在不到 O(n!) 的时间内完成它？

Thanks

你的贪心算法IS正确的。 我们可以通过证明任何其他覆盖只能通过用您的算法生成的覆盖替换它来改进它来证明这一点。

令 C 为给定输入的有效覆盖（不一定是最佳输入），并令 S 为根据您的算法的覆盖。现在让我们检查点 p1、p2、... pk，它们代表您在每个迭代步骤中处理的最小点。覆盖层 C 也必须覆盖它们全部。观察到 C 中没有任何线段覆盖其中的两个点；否则，你的算法会选择这个片段！因此，|C|>=k。您的算法的成本（段数）是多少？ |S|=k。

这样就完成了证明。

两个注意事项：

1）实现：用n[0]初始化bestLine是不正确的，因为循环可能无法改进它，并且n[0]不一定覆盖minX。

2）实际上这个问题是一个简化版本设置封面 http://en.wikipedia.org/wiki/Set_cover问题。虽然原始模型是 NP 完全的，但这种变化结果是多项式的。