我正在尝试解决这个问题，但我被困在如何使这项工作上。我将发布问题，然后解释我在其中的位置。
给定一组总大小为 n 的水平线段和垂直线，我们要计算与每条垂直线相交的水平线段的数量。该算法的复杂度应该是 O(n*logn)，并且应该通过排序来实现，然后是线性扫描。水平线段由两个 x 坐标和一个 y 坐标指定，而垂直线由单个 x 坐标指定。输出是一个数字数组 count[l]，每个垂直线 l 一个。
对于排序，我想我会按照最早完成的行（即最小的第二个 x 坐标，或者在垂直线的情况下，只是它的一个 x 坐标）对整个集合进行排序，这样我就有一个线性进展所有的行。我只是对如何进行排序后的线性扫描感到困惑。如果有人有任何提示、提示或指南，我将不胜感激！
PS：这是期中练习，虽然不一定是作业，但我还是会这样标记。
这个问题可以写成其他方式：
Foreach 水平线段 (x1,x2)，找到与其相交的所有垂直线。您可以通过对获得一组位置 x 的垂直线进行排序来做到这一点。
现在，运行二分查找并在 x 的集合中定位 x1，我们称其位置为 p1。对 x2, p2 执行相同的操作。给定段的交叉点数等于 p2-p1。
对所有水平段执行此操作。
对垂直段进行排序将花费 O(klog(k))。每次搜索都在 O(log(k)) 中完成，并且对每个段进行两次：O(mlog(k))。其中 k 是垂直线的数量，m 是水平线段的数量。n = m+k > m,k 因此，整体复杂度为 O(nlogn)。
首先，您放置水平线段的所有起点/终点。和垂直线的 x 坐标一起。
其次，对它们进行排序。我们称之为排序列表L。
三、成像有一条垂直扫描线，从你点列表的最左边开始，L向右移动。
每当扫描线碰到一个点，它要么是水平线段的起点，要么是水平线段的终点，要么是垂直线。
移动扫描线时可以做两件事：
1）保留扫描线当前相交的水平线段集合（只要它是水平线段的起点/终点，将其添加到集合中/从集合中删除）
2）只要它是一条垂直线，您就知道垂直线与您在 1）中维护的集合中的所有水平线段相交
所以，排序是 O(nlogn); 在排序列表中移动扫描线L是 O(n)
总而言之，它是 O(nlogn)