重叠区间子集的最大数量
Maximum number of subsets of overlapping intervals
给定一组区间 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) 或大大小于 [=22= 中获得此映射]o(n2)?
似乎有一种 O(n*log(n)) 的方法可以做到这一点。直觉是我们需要某种方式来组织区间，在当前步骤中，当前区间可能包含的所有区间都已被考虑。
算法如下：
- 按结束时间升序排列区间，并按开始时间降序排列并列的结束时间。
- 遍历间隔并维护一组已排序的所有开始时间。这个想法是，在查看当前区间时，它 可能 包含的所有区间都已经被检查过，而当前区间包含的区间数只是元素的数量在我们构建的集合中，开始时间比当前集合晚。
遍历示例，我们首先发现
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))，假设使用高效排序和平衡树在第二部分。在给定的时间内初始排序 运行s。第二部分涉及 n 插入高度为 O(log(n)) 的二叉树，给出 运行 时间 O(nlog(n))。因为我们在 O(nlog(n)) 中对 运行 的两个步骤求和，所以总的 运行 时间是 O(nlog( n)).
给定一组区间 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) 或大大小于 [=22= 中获得此映射]o(n2)?
似乎有一种 O(n*log(n)) 的方法可以做到这一点。直觉是我们需要某种方式来组织区间，在当前步骤中，当前区间可能包含的所有区间都已被考虑。
算法如下：
- 按结束时间升序排列区间，并按开始时间降序排列并列的结束时间。
- 遍历间隔并维护一组已排序的所有开始时间。这个想法是，在查看当前区间时，它 可能 包含的所有区间都已经被检查过，而当前区间包含的区间数只是元素的数量在我们构建的集合中，开始时间比当前集合晚。
遍历示例，我们首先发现
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))，假设使用高效排序和平衡树在第二部分。在给定的时间内初始排序 运行s。第二部分涉及 n 插入高度为 O(log(n)) 的二叉树，给出 运行 时间 O(nlog(n))。因为我们在 O(nlog(n)) 中对 运行 的两个步骤求和，所以总的 运行 时间是 O(nlog( n)).