http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf 我在做这些问题的实践中，我碰到一个难倒我。

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf I was doing these questions for practice where I came across one that stumped me.

7.（a）假设我们正在给定的n线段的平面，其中每个段具有上直线y = 0和1端点一个端点的集合L   上直线y = 1，并且所有2n个端点是不同的。描述和   分析的算法来计算的L最大子集，其中没有   对段相交。

7.(a) Suppose we are given a set L of n line segments in the plane, where each segment has one endpoint on the line y = 0 and one endpoint on the line y = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.

（b）假设我们正在给定的n线段的一组L的平面上，   其中每一个区段的谎言在单位圆终点X 2 + Y 2 =   1，并且所有2n个端点是不同的。描述和分析的   算法计算升最大子集，其中没有一对   段相交。

(b) Suppose we are given a set L of n line segments in the plane, where the endpoints of each segment lie on the unit circle x 2 + y 2 = 1, and all 2n endpoints are distinct. Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects.

我想通了，该怎么办7A，（这个问题是一个变相的问题找到越来越多的最大的子集），在为O（n log n）的时间。林几乎接近放弃对7B，因为我不能想出一个办法做到这一点。

I figured out how to do 7a, (the question is a disguised problem to find the largest subset of increasing numbers), in O(n log n) time. Im almost close to giving up on 7b, as I cant figure out a way to do it.

不过，有一个方法来转换7B的premise的东西更像7A的？我觉得这是接近问题的正确方法，并在弄清这一点任何帮助将是非常美联社preciated。

However, is there a way to convert 7b's premise to something more like 7a's? I feel like that's the right way of approaching the problem, and any help in figuring this out would be much appreciated.

推荐答案

我不能拿出一个为O（n *日志（n））的算法，但这里是一个为O​​（n 2 ）之一。

I couldn't come up with an O(n*log(n)) algorithm, but here is an O(n2) one.

我们的想法是，我们建立了一个有向图顶点重新从给定的presenting段和边缘重新presenting的谎言的权利的关系。

The idea is that we build a directed graph with vertices representing segments from the given set and edges representing the "lies to the right of" relation.

让L为部分名单：{（A 1 ，B 1 ），（A 2 ，B 2 ），...，（一个 N ，B N ）}，其中 K 和b K 是第k段的终点。

Let L be the list of segments: {(a1, b1), (a2, b2), ..., (an, bn)}, where ak and bk are k-th segment's endpoints.

让L'是段的列表：{（A 1 ，B 1 ），（B 1 ，一个 1 ），（A 2 ，B 2 ），（B 2 ，一个 2 ） ，...，（一个 N ，B N ），（B N ，一个 N ）}。

Let L' be the list of segments: {(a1, b1), (b1, a1), (a2, b2), (b2, a2), ..., (an, bn), (bn, an)}.

让图的顶点具有指数从1到2 * n构成，索引k重新presenting段L'〔k]的，即（一 K / 2 ，B K / 2 ）如果k为奇数，并且（b K / 2 ，一 K / 2 ）如果k是偶数。

Let the vertices of the graph have indices from 1 to 2*n, each index k representing the segment L'[k], i.e. (ak/2, bk/2) if k is odd, and (bk/2, ak/2) if k is even.

一个段（A 1 ，B 1 ），据说是骗一个段（右一 2 ，B 2 ），当分 1 ，一个 2 ，B 2 ，B 1 的放置在单位圆上按顺时针顺序。

A segment (a1, b1) is said to lie to the right of a segment (a2, b2) when the points a1, a2, b2, b1 are placed in a clockwise order on the unit circle.

请注意：1）如果一个段谎言到别人的权利，他们不相交; 2）如果从L-两个段不相交，2由L四个相应段的不一定位于一个的另一个的权利; 3）任何一组的非相交由L区段是由一系列的L段的定义，每个卧的previous 1的右侧。

Note that 1) If one segment lies to the right of another, they don't intersect; 2) If two segments from L don't intersect, two of the four corresponding segments from L' necessarily lie one to the right of another; 3) Any set of non-intersecting segments from L is defined by a series of segments of L', each lying to the right of the previous one.