例如，当在x，y坐标中以（x-left，x-right，y）的形式给出点时，（1,5,3），（2,4,5）返回（1,2,3） ，（2,4,5），（4,5,3）
解决此问题的最简单有效（O（N log N））方法是使用“线扫描”算法。
想象一下，在整个集合中从左到右扫描一条垂直线，跟踪它穿过的最顶部区域。每当最顶部的部分发生变化时，这是一个可能影响顶部船体的重要事件。从这些变化列表中计算顶壳是很容易的。
请注意，这些重要事件只能发生在其中一个输入段开始或结束的x位置。因此，我们只需考虑在这些x位置发生的情况，而不是平滑地扫描线。所以：
一个直截了当的贪婪算法可以很好地解决这个问题。按y坐标，降序对段进行排序; CA ;;这个名单seg。现在......
top_hull = [empty set]
while seg is not empty
head = seg.pop() // pop off the highest segment.
top_hull += head
for each segment in seg
remove the interval (head.xleft, head.y-left) from segment
请注意，在少数情况下可以删除间隔：
`head`'s interval does not overlap `segment`
no action
`head`'s interval contains `segment`
remove segment
`segments`'s interval contains `head` (both ends stick out
split segment into the two remaining pieces.
`head`'s interval overlaps one end of `segment`
truncate segment
根据您的实现语言，间隔代数可能有很好的支持包。
修剪答案有正确的想法，但我觉得解释如何检查间隔重叠是不公平的。实际上，算法的那部分在二次时间O(n^2)中运行，因为它在某个点形成所有n^2对，这是不必要的。我会做什么 -
首先，从段列表中创建最大堆，以y坐标为键。您可以在O(logn)时间中提取和删除最大值，因此这与排序的时间复杂度相同，只需使用popping builtin。
heap = max_heap(segement_list)
output = []
while heap is not empty
segment = heap.pop() # max / highest
# trim / split segment
# append trimmed segment(s)
现在我们只需要修剪细分。我们将使用另一种数据结构来快速查询潜在的交叉点，而不是将其与其他所有段配对并根据需要进行修剪。我们将每个添加的段存储在二叉搜索树中，其中较低的x坐标作为其键。然后我们可以遍历这个树，寻找小于或等于我们即将添加的段的最大段（通过较低的x坐标）。
为了使以下段落的技术细节不那么臃肿，让我们来看看两个关键比较的实现细节。假设段a的lower_x值比b小（因为在下面的段落中，我们总是知道哪个更小）。
# boolean- do `a` and `b` intersect
function intersects(a, b)
return a.upper_x >= b.lower_x
# boolean- is `b` a subsegment of `a`
function is_subsegment(a, b)
return a.upper_x >= b.upper_x
我们还需要三个转换，使用相同的a和b定义 -
function merge(a, b)
a.upper_x = b.upper_x
function trim_left(a, b)
a.upper_x = b.lower_x
function trim_right(a, b)
b.lower_x = a.upper_x
回到查询BST的想法 - 在查询我们的段left_segment时获取segment，并查看它们是否相交。如果它们相交，检查segment的is_subsegment left_segment。如果是，则中止和continue到堆中的下一个段。否则，如果它们相交，我们需要trim_right segment。无论交叉与否，我们都会处理任何右侧交叉点。之后，我们可以merge修改segment（实际上subsegment，你会看到）与left_segment，如果他们重叠。
left_segment是唯一可以从左侧重叠的段，因为我们在插入BST时合并所有重叠段。然而，这并不适用于右侧，因为我们的segment尚未从右侧进行修剪。我们需要逐步处理修剪。
将right_segment作为树中left_segment之后的下一个片段（有序遍历）。制作一份名为segment的subsegment。如果subsegment与right_segment相交，trim_left它，将subsegment插入输出数组，合并两个段，并从BST中删除right_segment。否则，只需将subsegment插入数组即可。现在我们可以将subsegment与left_segment合并，如果它们重叠的话。如果没有，请将subsegment插入BST，并将变量left_segment分配给它。
现在我们重复这个过程，直到我们从segment突然出现is_subsegment的left_segment。然后，我们使用堆中的下一个段重复整个过程。
我们知道形成我们的最大堆并弹出最大n时间将导致O(nlogn)时间复杂度。棘手的部分是弄清楚处理交叉点的时间复杂性。观察我们处理的每个段，在处理并合并所有subsegments后，我们将BST总体上的大小增加至多一个。这是因为我们所有的subsegments在每次迭代时都会合并在一起，所以它们最终形成了一个大的部分。这意味着我们的BST不大于n，所以查询和删除/插入BST需要O(logn)时间。
另请注意，对于插入到BST中的每个段，它将仅与每个段相交一次 - 因为当它执行时，两个（或更多）将合并为单个新段。例外情况是当一个段是其left_segment的子段时，但是在这种情况下我们中止而不会发出任何新的段，所以它的大小+0的净变化无论如何。利用这些知识，结合先前的观察结果，即每个部分最终为BST最多贡献一个新的部分，我们可以得出结论，最多将有O(n)交叉点，因此插入/删除。所以O(nlogn)有时间维持我们的BST。
鉴于我们的其余操作是恒定的时间，我们的整体时间复杂度是O(nlogn)，而不是O(n^2)，当强制交叉和修剪。