我试图解决这个问题这里。

此外，张贴了一个问题：您将获得N个间隔的列表。 面临的挑战是选择时间间隔的最大子集，使得没有三个区间在子集共享一个公共点？

Also, posting the question: You are given a list of N intervals. The challenge is to select the largest subset of intervals such that no three intervals in the subset share a common point?

但不能回头，一个解决方案。这是我试过到目前为止：

but couldn't come around to a solution. This is what I tried so far:

难道你们给我的提示对如何处理这个问题，如果我缺少什么。对不起，我经过一个很长的时间做算法，并一直失去联系最近。

Could you guys give me hints on how to approach this problem or if I am missing anything. Sorry, I am doing algorithms after a really long time and been out of touch lately.

推荐答案

我给一般的话解决方案，无需编程了。

I'll give the solution in general words without programming it.

让我们表示段为S 1 ，S 2 ，...，S N 。他们开始为B 1 ，B 2 ，。B N ，以及他们为e端 1 ， Ë 2 ，... E N 。

Let's denote segments as s1, s2, ..., sn. Their beginnings as b1, b2,... bn, and their ends as e1, e2,... en.

排序段由他们开始，因此B 1 ＆LT; b 2 ＆LT; ...＆LT; b N 。它是足够进行检查，如果没有三段覆盖一个点的条件成立。我们会从B 1 这样的顺序为b N 。于是，开始与B 1 ，移动到下一个点，等一个接一个，直到在某个点b 我有三段覆盖它。这些都将是段S 我和另外两个人，让我们S个Ĵ和S K 。这三个细分市场中删除具有最大的终点，即最多{É我，E Ĵ，E K }。移动到下一个段的开头（二 i + 1的）。当我们到达b N 的过程就完成了。所有正在离开区段构成区段这样的最大子集，没有三段共享一个公共点。

Sort segments by their beginnings, so b1< b2<...< bn. It is enough to check them if the condition of no three segments covering a point holds. We will be doing so in the order from b1 to bn. So, start with b1, move to the next point, and so on one by one, until at some point bi there are three segments covering it. These will be the segment si and two others, let's say sj and sk. Of those three segments delete the one with the maximum end point, i.e. max{ei, ej, ek}. Move on to the beginning of the next segment (bi+1). When we reach bn the process is done. All the segments that are left constitute the largest subset of segments such that no three segments share a common point.

为什么这将是最大的子集。比方说，我们的解决方案是S（下集段）。假设有一个最佳的解S *。此外，排序S和S *段由他们开始的坐标。现在，我们将经历S中的段和S *，并比较它们的终点。用S的任意k建设日段S中的终止坐标为k比年底更小的坐标日段S *（E K ＆LT; = E K 的）。因此，S中的段数不大于S中的（朝着S *我们总是成功逃脱S）。

Why this will be the maximal subset. Let's say our solution is S (the set of segments). Suppose there is an optimal solution S*. Again, sort the segments in S and S* by the coordinate of their beginnings. Now, we will be going through the segments in S and in S* and comparing their end points. By the construction of S for any kth segment in S its end coordinate is smaller than the end coordinate of kth segment in S* (ek<=ek). Therefore, the number of segments in S is not less than in S (moving in S* we're always outrunning S).

如果这是不足够的说服力，尝试思考一个简单的问题，首先，在没有两段可以重叠。解决的方法是一样的，但它更直观地看到为什么它给出了正确的答案。

If this is not convincing enough, try to think about a simpler problem at first, where no two segments can overlap. The solution is the same, but it's much more intuitive to see why it gives the right answer.