algorithm - 计算飞行员将看到的在二维平面中相交的线数

Question

问题是这样的:

街道两边各有两座平行的建筑物。 N 根绳子从一栋楼的一层连接到另一栋楼的另一层 ((a[i],b[i]) ，其中 a[i] 是第一个建筑物的楼层，ith<​​ 绳索连接到该楼层，b[i] 是另一栋建筑物的楼层)。现在一架直升飞机正在接近大楼。他能看到多少个绳索交叉点？

您可以想象电影黑暗骑士中的隧道场景，当时一架 GCPD 直升机前来营救 Harvey dent 却被绳索勒死。

你可以想象二维平面中的交叉点。
在下面的图片中，飞行员只会看到一个十字路口。

方法

1. The one approach I could think of was brute-force, where I compare each rope with all the other ropes for the intersection. But want to do better than that.
2. I thought of sorting the ropes according to the points of contact on any one of the building but couldn't work out.

注意事项

1. No, it's not from any of the running competitions.
2. I just want an approach, not the code.

提前致谢。

Answer 1

将左端位置放入二叉搜索树(RB，AVL)，将右端位置放入排序数组/列表，设置对应树节点的链接(段A的右端知道A左端的节点)。

Walk through array
For every right end:
    get rank R of the left end node
    add (R-1) to result
    remove left end node from the tree

解释:线段确实与所有其他线段相交，其左端在上，右端在下