我想知道是否有比我想出的更有效的解决方案（尚未对其进行编码，但在底部描述了它的要点）。
编写一个函数 calcNthSmallest(n,intervals)，它将一个非负 int n 和一个区间列表 [[a_1; b_1]; : : : ; [是; b_m]] 并在将所有间隔与重复进行并集时计算第 n 个最小数字（从 0 开始）。例如，如果区间是 [1; 5]; [2; 4]; [7; 9]，它们与重复的结合将是[1; 2；2；3；3；4；4；5个；7; 8个；9]（注 2; 3; 4 各出现两次，因为它们都在区间 [1; 5] 和 [2; 4] 中）。对于这个区间列表，第 0 个最小的数字是 1，第 3 个和第 4 个最小的数字都是 3。即使 a_i; b_i 可以非常大（例如，一万亿），并且有几个区间
我想到的方法是直接的解决方案，即创建联合数组并遍历它。
这个问题可以在 O(N log N) 中解决，其中 N 是列表中的间隔数，而不考虑间隔端点的实际值。
有效解决此问题的关键是将可能重叠的区间列表转换为不相交或相同的区间列表。在给定的示例中，只需要拆分第一个区间：
{ [1,5], [2,4], [7,9]} =>
+-----------------+ +---+ +---+
{[1,1], [2,4], [5,5], [2,4], [7,9]}
（不过，这不必明确地完成：见下文。）现在，我们可以对新间隔进行排序，用计数替换重复项。由此，我们可以计算每个（可能重复的）区间所代表的值的数量。现在，我们只需要累积这些值来确定解决方案位于哪个区间：
interval count size values cumulative
in interval values
[1,1] 1 1 1 [0, 1)
[2,4] 2 3 6 [1, 7) (eg. from n=1 to n=6 will be here)
[5,5] 1 1 1 [7, 8)
[7,9] 1 3 3 [8, 11)
我将累积值写为半开区间的列表，但显然我们只需要端点。然后，我们可以通过例如对累积值列表进行二进制搜索来找到哪个区间包含值 n，我们可以通过从 n 中减去区间的开始然后除以数数。
应该清楚，上表的最大大小是原始间隔数的两倍，因为每一行都必须在原始列表中某个间隔的开始或结束处开始和结束。如果我们将区间写成半开而不是闭，这会更清楚；在这种情况下，我们可以断言表的精确大小将是端点集合中唯一值的数量。从这种洞察力中，我们可以看出我们根本不需要这张桌子。我们只需要排序的端点列表（尽管我们需要知道每个值代表哪个端点）。我们可以简单地遍历该列表，保持活动间隔数的计数，直到达到我们正在寻找的值。
这是一个快速的python实现。它可以改进。
def combineIntervals(intervals):
# endpoints will map each endpoint to a count
endpoints = {}
# These two lists represent the start and (1+end) of each interval
# Each start adds 1 to the count, and each limit subtracts 1
for start in (i[0] for i in intervals):
endpoints[start] = endpoints.setdefault(start, 0) + 1
for limit in (i[1]+1 for i in intervals):
endpoints[limit] = endpoints.setdefault(limit, 0) - 1
# Filtering is a possibly premature optimization but it was easy
return sorted(filter(lambda kv: kv[1] != 0,
endpoints.iteritems()))
def nthSmallestInIntervalList(n, intervals):
limits = combineIntervals(intervals)
cumulative = 0
count = 0
index = 0
here = limits[0][0]
while index < len(limits):
size = limits[index][0] - here
if n < cumulative + count * size:
# [here, next) contains the value we're searching for
return here + (n - cumulative) / count
# advance
cumulative += count * size
count += limits[index][1]
here += size
index += 1
# We didn't find it. We could throw an error
因此，正如我所说，该算法的运行时间与间隔的实际值无关；它仅取决于间隔列表的长度。这个特殊的解决方案是O(N log N)因为排序的成本（in combineIntervals）；如果我们使用优先级队列而不是完整排序，我们可以在其中构造堆，O(N)但O(log N)对每个扫描的端点进行扫描。除非N真的很大并且参数的期望值n相对较小，否则会适得其反。不过，可能还有其他方法可以降低复杂性。
编辑2：
这是对您问题的另一种看法。
让我们以图形方式考虑间隔：
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
[-------]
[-----------------]
[---------]
[--------------]
[-----]
当在下限上按升序排序时，我们可以得到类似于上面的区间列表的东西([2;10];[4;24];[7;17];[13;30];[20;27])。每个下限都表示一个新区间的开始，也将标志着数字重复的另一个“级别”的开始。相反，上限标记该级别的结束，并降低一个的重复级别。因此，我们可以将上述内容转换为以下列表：
[2;+];[4;+];[7;+][10;-];[13;+];[17;-][20;+];[24;-];[27;-];[30;-]
其中第一个值表示边界的等级，第二个值表示边界是下限 ( +) 还是上限 ( -)。第 n 个元素的计算是通过遵循列表来完成的，遇到下限或上限时提高或降低重复级别，并使用重复级别作为计数因子。
让我们再次以图形方式考虑列表，但作为直方图：
3333 44444 5555
2222222333333344444555
111111111222222222222444444
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
上面的视图与第一个视图相同，所有间隔都垂直排列。
1是第一个，2第二个等的元素。实际上，这里重要的是每个索引处的高度，对应于每个索引在所有区间的联合中重复的次数。
3333 55555 7777
2223333445555567777888
112223333445555567777888999
1 1 1 2 2 2 3
0-2-4--7--0--3---7-0--4--7--0
| | | | | | || | |
我们可以看到直方图块从区间的下限开始，到上限或下限前一个单位结束，因此必须相应地修改新符号。
对于包含n 个区间的列表，作为第一步，我们将列表转换为上面的符号（O(n)），并按递增的绑定顺序对其进行排序（O(nlog(n))）。然后计算数字的第二步在O(n)中，总平均时间在O(nlog(n) ) 中。
这是 OCaml 中的一个简单实现，使用1and-1代替 '+' 和 '-'。
(* transform the list in the correct notation *)
let rec convert = function
[] -> []
| (l,u)::xs -> (l,1)::(u+1,-1)::convert xs;;
(* the counting function *)
let rec count r f = function
[] -> raise Not_found
| [a,x] -> (match f + x with
0 -> if r = 0 then a else raise Not_found
| _ -> a + (r / f))
| (a,x)::(b,y)::l ->
if a = b
then count r f ((b,x+y)::l)
else
let f = f + x in
if f > 0 then
let range = (b - a) * f in
if range > r
then a + (r / f)
else count (r - range) f ((b,y)::l)
else count r f ((b,y)::l);;
(* the compute function *)
let compute l =
let compare (x,_) (y,_) = compare x y in
let l = List.sort compare (convert l) in
fun m -> count m 0 l;;
注意： - 如果寻求的数字高于间隔，上述函数将引发异常。下面的其他方法不考虑这种极端情况。- OCaml 中使用的列表排序功能是归并排序，它在O(nlog(n))中有效执行。
编辑：
看到您可能有非常大的间隔，我最初给出的解决方案（见下文）远非最佳。相反，我们可以通过转换列表来使事情变得更快：我们尝试通过搜索重叠列表来压缩间隔列表，并通过为间隔添加前缀、重叠的几倍以及为间隔添加后缀来替换它们。然后我们可以直接计算列表中每个元素所涵盖的条目数。查看上面的拆分（前缀、中缀、后缀），我们看到进行处理的最佳结构是二叉树。该树的节点可以选择具有前缀和后缀。所以节点必须包含：
i节点中的一个区间i列表中的重复次数，i i 有了这个结构，树就会自动排序。这是体现该树的 ocaml 类型的示例。
type tree = Empty | Node of int * interval * tree * tree
现在转换算法归结为构建树。
此函数从其组件中创建一棵树：
let cons k r lt rt =
the tree made of count k, interval r, left tree lt and right tree rt
此函数递归地在树中插入一个区间。
let rec insert i it =
let r = root of it
let lt = the left subtree of it
let rt = the right subtree of it
let k = the count of r
let prf, inf, suf = the prefix, infix and suffix of i according to r
return cons (k+1) inf (insert prf lt) (insert suf rt)
构建树后，我们对树进行前序遍历，使用节点的计数来加速第 n 个元素的计算。
下面是我之前的回答。
以下是我的解决方案的步骤：
dq（或在某些时候反转的列表）来存储间隔这是代码：
let lower i = lower bound of interval i
let upper i = upper bound of i
let il = sort of interval list
i <- 0
j <- lower (head of il)
loop on il:
i <- i + 1
let h = the head of il
let il = the tail of il
if upper h > j then push h to dq
if lower h > j then
il <- concat dq and il
j <- j + 1
dq <- empty
loop
if i = k then return j
loop
该算法通过简单地遍历区间来工作，仅考虑相关区间，并计算i联合中元素的等级和该元素的值j。当达到目标排名k时，返回该值。
复杂度大致在 O(k) + O(sort(l)) 中。
如果我正确理解了你的问题，你想在区间列表中找到第 k 个最大的元素。如果我们假设 list 的 no = 2，那么问题是：在两个排序数组的联合中找到第 k 个最小的元素（其中区间 [2,5] 只不过是从 2 到 5 {2,3,4,5} 的元素) 这个解决方案可以在(n+m)log(n+m) 时间内解决，其中 (n 和 m 是列表的大小) 。其中 i 和 j 是列表迭代器。
Maintaining the invariant
i + j = k – 1,
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.
详情请点击这里
现在的问题是，如果您没有 list=3 个列表，那么
Maintaining the invariant
i + j+ x = k – 1,
i + j=k-x-1
The value k-x-1 can take y (size of third list, because x iterates from start point of list to end point) .
problem of 3 lists size can be reduced to y*(problem of size 2 list). So complexity is `y*((n+m)log(n+m))`
If Bj-1 < Ai < Bj, then Ai must be the k-th smallest,
or else if Ai-1 < Bj < Ai, then Bj must be the k-th smallest.
因此，对于大小为 n 的问题列表，复杂度为 NP 。
但是，是的，如果我们知道 k< sizeof(some lists) 我们可以在那些大小大于 k 的列表中从第 k+1 个元素开始到结束（从我们的搜索空间）截断元素（我认为它），我们可以做一些小的改进对大 k 没有帮助。如果有任何错误，请告诉我。
让我用一个例子来解释一下：假设我们有这些区间 [5,12],[3,9],[8,13]。这些区间的并集是：
number : 3 4 5 5 6 6 7 7 8 8 8 9 9 9 10 10 11 11 12 12 13.
indices: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
当lowest输入 9 时，将返回 11。
当highest输入 9 时，将返回 14。
最低和最高函数只是检查 x 是否存在于该区间中，如果存在则添加 xa（区间的下索引）以返回该特定区间的值。如果一个区间完全小于 x，则将该区间中的元素总数添加到返回值。
传递 13 时，find 函数将返回 9。
find 函数将使用二分查找的概念来查找第 k 个最小的元素。在给定的范围 [0,N] 中（如果没有给出范围，我们可以在 O(n) 中找到高范围）找到中间值并计算中间值的最低值和最高值。如果给定 k 介于最低和最高之间，则返回 mid else 如果 k 小于或等于下半部分的最低搜索 (0,mid-1)，否则在上半部分搜索 (mid+1,high)。
如果区间数为n，范围为N，则该算法的运行时间为n*log(N)。我们将找到最低和最高（以 O(n) 运行）log(N) 次。
//Function call will be `find(0,N,k,in)`
//Retrieves the no.of smaller elements than first x(excluding) in union
public static int lowest(List<List<Integer>> in, int x){
int sum = 0;
for(List<Integer> lst: in){
if(x > lst.get(1))
sum += lst.get(1) - lst.get(0)+1;
else if((x >= lst.get(0) && x<lst.get(1)) || (x > lst.get(0) && x<=lst.get(1))){
sum += x - lst.get(0);
}
}
return sum;
}
//Retrieve the no.of smaller elements than last x(including) in union.
public static int highest(List<List<Integer>> in, int x){
int sum = 0;
for(List<Integer> lst: in){
if(x > lst.get(1))
sum += lst.get(1) - lst.get(0)+1;
else if((x >= lst.get(0) && x<lst.get(1)) || (x > lst.get(0) && x<=lst.get(1))){
sum += x - lst.get(0)+1;
}
}
return sum;
}
//Do binary search on the range.
public static int find(int low, int high, int k,List<List<Integer>> in){
if(low > high)
return -1;
int mid = low + (high-low)/2;
int lowIdx = lowest(in,mid);
int highIdx = highest(in,mid);
//k lies between the current numbers high and low indices
if(k > lowIdx && k <= highIdx) return mid;
//k less than lower index. go on to left side
if(k <= lowIdx) return find(low,mid-1,k,in);
// k greater than higher index go to right
if(k > highIdx) return find(mid+1,high,k,in);
else
return -1; // catch statement
}
可以计算列表中有多少数字小于某个选定的数字 X（通过遍历所有间隔）。现在，如果这个数大于n，则解肯定小于X。同样，如果这个数小于或等于n，则解大于或等于X。根据这些观察，我们可以使用二分搜索.
下面是一个Java实现：
public int nthElement( int[] lowerBound, int[] upperBound, int n )
{
int lo = Integer.MIN_VALUE, hi = Integer.MAX_VALUE;
while ( lo < hi ) {
int X = (int)( ((long)lo+hi+1)/2 );
long count = 0;
for ( int i=0; i<lowerBound.length; ++i ) {
if ( X >= lowerBound[i] && X <= upperBound[i] ) {
// part of interval i is less than X
count += (long)X - lowerBound[i];
}
if ( X >= lowerBound[i] && X > upperBound[i] ) {
// all numbers in interval i are less than X
count += (long)upperBound[i] - lowerBound[i] + 1;
}
}
if ( count <= n ) lo = X;
else hi = X-1;
}
return lo;
}