arrays - 给定一系列范围，找到覆盖的总距离？

Question

这是我听说的一个面试问题。您有一系列数组，其中元素长度为两个数组，起点和终点在数字线上。可以有重叠。您需要返回覆盖的总距离。你会如何解决这个问题？

例子:输入:[[3,5], [1,3], [2,4]]输出:4

我的想法:您需要跟踪涵盖的范围以及某个值是否在特定范围内。虽然不太确定该怎么做？

Answer 1

您需要合并您的起始间隔，一旦它们合并，只需将总距离计算为每个间隔中覆盖的距离之和。

您可以在 O(n * log n) 中合并间隔，其中 n 是间隔数。为此，您可以根据第一点/第二点对它们进行排序。现在您遍历排序的间隔并检查应该合并哪一个。要了解为什么以及如何合并它们，请绘制如下内容:

a---------------------b
            c-------------------d

并注意合并区间的相似性。提示 max(a,c) > min(b,d)。

P.S.如果你想通过面试，多想想这个问题是有道理的。