algorithm - 重叠区间的最大子集数

Question

给定一组区间 S 找到 的有效方法是什么？子集数 分配给集合 S 中的每个区间。
例如说

S = (11,75), (14,62), (17,32), (24,48), (31,71), (34,74), (40,97), (41,58)

至于输出

(11, 75) => 6 -> (14,62), (17,32), (24,48), (31,71), (34,74), (41,58)  
(14, 62) => 3 -> (17,32), (24,48), (41,58)   
(17, 32) => 0  
(24, 48) => 0  
(31, 71) => 1 -> (41,58)   
(34, 74) => 1 -> (41,58)  
(40, 97) => 1 -> (41,58)  
(41, 58) => 0

是否可以在 中获得此映射？ o(nlogn) 或大大低于 o(n2) ?

Answer 1

好像有一个 O(n*log(n)) 方法来做到这一点。直觉是我们需要某种方式来组织区间，在当前步骤中，当前可能包含的所有区间都已被考虑在内。
算法如下:

按结束时间升序对间隔进行排序，并按开始时间降序对绑定(bind)的结束时间进行排序。

遍历间隔并维护所有看到的开始时间的排序集。这个想法是，在查看当前区间时，它可能包含的所有区间都已被检查过，当前区间确实包含的区间数只是我们构建的集合中稍后开始时间的元素数比现在的。

通过这个例子，我们首先发现 sortedIntervals = [(17,32), (24,48), (41,58), (14,62), (31,71), (34,74), (11,75),(40,97)]并让我们排序的间隔集(现在按开始时间排序)是 examinedIntervals = []现在让我们逐步了解 sortedIntervals

考虑(17,32) . examinedIntervals是空的，所以它不包含任何东西。

考虑(24, 48) . examinedIntervals = [(17, 32)] .因为没有从 24 开始的区间，所以我们有 (24, 48)包含 0 个区间。

考虑(41, 58) . examinedIntervals = [(17, 32), (24, 48)] .没有间隔在 41 之后有开始时间，所以 (41, 58)包含 0 个区间

考虑(14, 62) . examinedIntervals = [(17, 32), (24, 48), (41, 58)] .现在所有三个间隔的开始时间都在 14 之后，所以 (14, 62)包含 3 个区间

考虑(31, 71) . examinedIntervals = [(14, 62), (17, 32), (24, 48), (41, 58)] . 31 之后只有一个区间，所以 (31, 71)包含 1 个区间

考虑(34, 74) . examinedIntervals = [(14, 62), (17, 32), (24, 48), (31, 71), (41, 58)] .一个间隔在 34 之后，所以 (34, 74)包含 1 个区间

考虑(11, 75) . examinedIntervals = [(14, 62), (17, 32), (24, 48), (31, 71), (34, 74), (41, 58)] ，并且所有 6 个间隔的开始时间都在 14 之后。

考虑(40, 97) . examinedIntervals = [(11, 75), (14, 62), (17, 32), (24, 48), (31, 71), (34, 74), (41, 58)] .只有一个间隔出现在 40 之后，所以 (40, 97)包含 1 个区间。

总结一下，我们确实得到了正确的结果:

(40, 97) -> 1
(11, 75) -> 6
(34, 74) -> 1
(31, 71) -> 1
(14, 62) -> 3
(41, 58) -> 0
(24, 48) -> 0
(17, 32) -> 0

也可以很容易地验证运行时是 O(n*log(n)) ，假设在第二部分中使用了高效排序和平衡树。初始排序在给定的时间内运行。第二部分涉及 n 插入高度为 的二叉树O(log(n)) , 运行时间为 O(nlog(n)) .因为我们将在 中运行的两个步骤相加。 O(nlog(n)) ，总运行时间为 O(nlog(n)) .