我遇到了一个很好的问题，而preparing了一些编程的采访。

I came across a good question while preparing for some programming interviews.

给定一组可能重叠的区间，你需要写一个函数返回所有基本区间当中。例如：如果您在给定的间隔对下面的列表：{{1,5}，{3,10}，{5,11}，{15,18}，{16,20}}，那么你需要返回以下内容：

Given a set of possibly overlapping intervals, you need to write a function to return all elementary intervals among them. For example: if you are given intervals as the following list of pairs: {{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}, then you need to return the following:

{{1,3}，{3,5}，{5,10}，{10,11}，{15,16}，{16,18}，{18,20}}

{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20}}

请注意在上面的回答如下：

Note the following in the above answer:

的时间间隔{11,15}中省略了答案，因为它是 不存在在输入 从输入间隔{1,5}被分成{1,3}，{3,5} 在因为起点的回答3{3,10}定义 该切割的间隔成两个基本区间的投入。 The interval {11,15} is omitted in the answer because it is non-existent in the input. The interval {1,5} from the input has been split up into {1,3}, {3,5} in the answer because of the starting point "3" defined in {3,10} in the input that cuts the interval into two elementary intervals.

在Java方法签名：

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals)

一，我想象与输入到分离成不相交集，然后简单的O（NlogN）排序过的所有数字在每个不相交的组将产生的答案的解决方案。有没有更有效的方法来做到这一点？

One of the solutions that I imagined was to separate the input into non-intersecting sets, and then a simple O(NlogN) sort over all numbers in each non-intersecting set will yield the answer. Is there a more efficient way to do it?

推荐答案

您可以打破这一问题成区间套，再处理每个单独筑巢。通过嵌套的，我的意思是间隔共享至少一个点。对于例如，你给了：

You could break this problem up into nested intervals first, then deal with each nesting separately. By nested, I mean intervals that share at least one point. For the example you gave:

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}

有两个嵌套：

there are two nestings:

{1,5}, {3,10}, {5,11}

和

{15,18}, {16,20}

在一般情况下，确定嵌套，您可以根据左端点的时间间隔一个新的嵌套每当你看到排序（如在你的例子），然后运行通过，并启动 {X，Y} {X'，Y'} 与 Y'LT; X'。

In general, to determine the nestings, you can sort the intervals based on the left endpoint (as in your example), then run through and start a new nesting whenever you see {x,y}, {x',y'} with y < x'.

对于嵌套的基本周期是由值的排序序列（不重复）形成。在该示例中，嵌套给

For a nesting, the "elementary intervals" are formed by the sorted sequence (without repeats) of values. In the example, the nestings give

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11}

和

(15,16,18,20) -> {15,16}, {16,18}, {18,20}

因此​​整体的算法可能是这样的：

So the overall algorithm may look like this:

在排序的基础上左端点的时间间隔 通过间隔运行，直到 {X，Y}，{X'，Y'} 与 Y'LT; X' 从开始到 {X，Y} ，使端点排序列表（没有重复），说 A0，A1，...， AK 在加入基本间隔 {AI，一个第（i + 1）} 为 I = 0 ... K-1 删除间隔可达 {X，Y} 键，从第2步继续 Sort the intervals based on the left endpoint Run through intervals until {x,y}, {x',y'} with y < x' From beginning to {x,y}, make sorted list of endpoints (no repeats), say a0,a1,...,ak Add elementary intervals {ai,a(i+1)} for i = 0...k-1 Remove intervals up to {x,y} and continue from step 2