给定n个水平线段，其中每个线段的范围是x2 - x1，我应该应用什么算法来获得一条直线，它让我获得最大的 combined 范围（每个线段与一个线段相加会增加该线段的范围），就像发现一样钻一条线，以获得最大量的水（水代表具有X2-X1数量的区段）我完成了蛮力算法，令人沮丧 big O (n^4)
我将假设没有段在另一个段的末尾开始，如果不是，则需要修改以下内容：
对于每个段，创建2个元组：（x1，index）和（x2，index）
按元组的第一个值对元组进行排序
设置最佳= 0
迭代元组 . 如果它是起始点（之前没有看到索引），则将其值（x2 - x1）添加到最佳值 . 如果它是一个终点，则将其值减去最佳值 .
问题的答案将是最佳达到的最高值 .
复杂性：O（n log n）
1 回答
我将假设没有段在另一个段的末尾开始，如果不是，则需要修改以下内容：
对于每个段，创建2个元组：（x1，index）和（x2，index）
按元组的第一个值对元组进行排序
设置最佳= 0
迭代元组 . 如果它是起始点（之前没有看到索引），则将其值（x2 - x1）添加到最佳值 . 如果它是一个终点，则将其值减去最佳值 .
问题的答案将是最佳达到的最高值 .
复杂性：O（n log n）