algorithm - 找到一个有效的算法来得到一条线

Question

给定n个水平线段，其中每个线段的范围是x2 - x1，我应该应用什么算法来获得一条直线，使我获得最大的组合范围（与线段的每个交叉点都增加了该线段的范围），就像发现一条要钻的线，以获得最大量的水（水代表具有 X2-X1 数量的段）我以令人沮丧的大 O (n^4)完成了蛮力算法

标签： algorithmtime-complexitybig-o

Answer 1

我将假设没有从另一个结尾开始的段，如果没有，则需要修改以下内容：

• 对于每个段，创建 2 个元组：(x1, index) 和 (x2, index)
• 按元组的第一个值对元组进行排序
• 设置最佳 = 0
• 迭代元组。如果它是起点（以前没有见过索引），则将其值 (x2 - x1) 添加到最佳值。如果它是一个端点，则将其值减去最佳值。
• 问题的答案将是最好达到的最高值。

复杂度：O(n log n)