找出最大相交线数

Question

给定 n 条直线 (x1,x2) ，其中 x1 是起点，x2 是平行于 x 轴的直线的终点。我们需要画一条垂直于 X 轴的线，使其与最大数量的线（平行于 X 轴）相交。如何找到相交线的坐标和最大相交数。

谁能提供一些解决此问题的提示？

Answer 1

除非线是拉伸的（有限长度 - 我希望这是正确的术语），否则垂直于 X 轴的任何线都符合要求。假设它们是拉伸：

define line: int x_l , int x_r //representation of a line (y-coordinates aren't necessary)

define mostLinesX:
    input: list coords
    output: xOpt

    Map<Integer , Integer> growthMap

    for line l in coords
        put(growthMap , l.x_l , 1)
        put(growthMap , l.x_r , -1)

    int maxX = -1
    int max = 0
    int curCt = 0
    for int i in sorted(growthMap.keys)
        curCt += get(growthMap , i)

        if curCt > max
            maxX = i
            max = curCt

     return maxX

基本思路非常简单：定义一个函数 f(x)，显示将与 x 处的垂直线相交的线数。此函数的结果是从 x 之前开始的所有行数减去在 x 之前结束的所有行数。现在算法要做的就是找到 f(x) 的峰值。 x 将始终是最小的可能值，这样就找不到符合条件的更大的 x。

注意：行尾是唯一的。因此，如果我们有一行 (a , b)，b 本身不是该行的一部分 - 或者换句话说：(a , a + 1) 的长度为 0.

找出最大相交线数

Find the maximum number of lines intersecting

algorithm

dynamic-programming

data-structures