algorithm - 找到区间的最大子集

Question

我正在尝试解决这个问题here .

此外，发布问题:您将获得一个包含 N 个间隔的列表。 挑战是选择最大的间隔子集，使得子集中没有三个间隔共享公共(public)点？

但无法找到解决方案。这是我到目前为止尝试过的:

1. DP:不认为问题有重叠的子问题，所以这不起作用
2. 将其简化为一个图，每个点都是一个顶点，区间是无向图的边。然后问题就简化为在图中找到最大长度的不相交路径。也想不出一个巧妙的方法来做到这一点
3. 尝试将其减少为网络流量，但效果不佳。

你们能给我一些关于如何解决这个问题的提示或者我是否遗漏了什么。抱歉，我做算法已经很久了，最近没有联系。

Answer 1

我将笼统地给出解决方案，而无需对其进行编程。

让我们将段表示为 s₁、s₂、...、s_n。它们的开头为 b₁、b₂、... b_n，结尾为 e₁， e₂,... e_n.

按开头对段进行排序，因此 b₁< b₂<...n。如果没有三个线段覆盖一个点的条件成立，检查它们就足够了。我们将按照从 b₁ 到 b_n 的顺序执行此操作。因此，从 b₁ 开始，移动到下一个点，依此类推，直到某个点 b_i 有三个线段覆盖它。这些将是段 s_i 和另外两个段，比方说 s_j 和 s_k。在这三个段中删除具有最大终点的一个，即 max{e_i, e_j, e_k}。移至下一段的开头 (b_i+1)。当我们到达 b_n 时，该过程就完成了。剩下的所有线段构成线段的最大子集，使得没有三个线段共享公共(public)点。

为什么这将是最大子集。假设我们的解决方案是 S(线段集)。假设存在最优解S*。再次，按起始坐标对 S 和 S* 中的段进行排序。现在，我们将遍历 S 和 S* 中的段并比较它们的端点。通过构造 S，对于 S 中的任何第 k^th 段，其结束坐标都小于 S* 中第 k 段的结束坐标(e_k<=e_k)。因此，S 中的段数不少于 S(在 S* 中移动，我们总是超过 S)。

如果这还不够令人信服，请首先尝试考虑一个更简单的问题，其中两个线段不能重叠。解决方案是相同的，但更直观地看出为什么它给出了正确的答案。