我正在尝试解决这个问题，其中给出了 N (N<=1000) 个间隔，并且算法应该计算（大小）最大的间隔子集，使得子集中没有三个间隔共享一个公共点。现在我只在寻找动态编程算法。
我的想法是通过完成时间对间隔进行排序，然后考虑以下子问题： A[i] - 仅使用前 i 个间隔的问题的解决方案（即最大间隔数）。
现在我的问题是关于复发的：如果采用第 i 个间隔，那么我无法弄清楚复发。
有人可以解释我在哪里做错了吗（是子问题定义还是我只是在重复子问题上遗漏了一些东西）？
编辑（新想法？）
经过一些研究，我找到了通用工作选择算法的这个DP 解决方案。所以下一个想法是有一个q数组，其中q[i]= 与第 i 个区间没有重叠的最后一个区间的索引。然后可以肯定的是，当采用第 i 个间隔时，计算 A[i] 的公式类似于（注意缺少的部分）：
A[i] = 1 + A[q[i]] + [missing-part];
//1 stands for the i-th interval
//A[q[i]] stands for the solution of the intervals that do not overlap with with the i-th interval
//[missing-part] is the maximum number of intervals from the intervals that overlap with the i-th intervals that are safe to be added.
问题仍然存在：如何计算缺失的部分？
编辑（贪婪的解决方案，而不是想要的解决方案） 贪婪的解决方案非常简单，非常类似于Job Selection Problem，并额外检查在添加新间隔时，必须没有未处理的间隔破坏问题的条件。