找到包含整数的第 k 个最短区间
finding the kth shortest interval containing an integer
我面临以下问题：我需要编写一个程序，将 n 区间 [a,b] 和 m 对 (k,d) 作为输入。对于每个 (k,d) 对，程序应输出第 k 个最短区间的长度（其中区间的长度定义为 b - a + 1），其中 a <= d <= b。如果 d 不在任何区间内，或者 d 在小于 k 区间内，程序应该输出 -1.
示例input/output：
第一个整数（5）表示n。接下来的 n 行包含间隔（因此 [2..4]、[2..6] 等）。下面是整数 m (3)，后跟 m 行 (k,d).
我正在寻找能够尽快解决这个问题的算法。
这可以在 O((n + m) log n) 中解决sweep line algorithm.
的时间
扫描线算法设置一个定时事件列表，然后按排序顺序处理它。对于这个问题，每个区间 [a, b] 在时间 a 引起一个开始事件以及时间 b 的停止事件。每个查询 (k, d) 在时间 d 引起一个查询事件。由于区间是完全闭合的，所以每次我们处理开始事件，然后查询事件，然后停止事件。
我们维护一个由扫描点刺穿的间隔长度的排序列表。要处理开始事件，请将间隔的长度添加到列表中。要处理停止事件，请从列表中删除间隔的长度。要处理查询事件，请检索列表的 kth 元素。在 O(log n) 时间内支持所有这些操作的排序列表数据结构是一个红黑树，其中每个节点包含其左子树中的节点数。这几乎是树扩充的典型示例，因此 CLRS 和许多其他来源应该有详细信息。
我面临以下问题：我需要编写一个程序，将 n 区间 [a,b] 和 m 对 (k,d) 作为输入。对于每个 (k,d) 对，程序应输出第 k 个最短区间的长度（其中区间的长度定义为 b - a + 1），其中 a <= d <= b。如果 d 不在任何区间内，或者 d 在小于 k 区间内，程序应该输出 -1.
示例input/output：
第一个整数（5）表示n。接下来的 n 行包含间隔（因此 [2..4]、[2..6] 等）。下面是整数 m (3)，后跟 m 行 (k,d).
我正在寻找能够尽快解决这个问题的算法。
这可以在 O((n + m) log n) 中解决sweep line algorithm.
的时间扫描线算法设置一个定时事件列表，然后按排序顺序处理它。对于这个问题，每个区间 [a, b] 在时间 a 引起一个开始事件以及时间 b 的停止事件。每个查询 (k, d) 在时间 d 引起一个查询事件。由于区间是完全闭合的，所以每次我们处理开始事件，然后查询事件，然后停止事件。
我们维护一个由扫描点刺穿的间隔长度的排序列表。要处理开始事件，请将间隔的长度添加到列表中。要处理停止事件，请从列表中删除间隔的长度。要处理查询事件，请检索列表的 kth 元素。在 O(log n) 时间内支持所有这些操作的排序列表数据结构是一个红黑树，其中每个节点包含其左子树中的节点数。这几乎是树扩充的典型示例，因此 CLRS 和许多其他来源应该有详细信息。