将区间插入不相交的区间集合

给定排序的不相交集合(p,q）其中‘p’是开始时间，‘q’是结束时间。你会得到一个输入间隔。将它插入正确的地方。并返回结果排序的不相交集合。将区间插入不相交的区间集合

Eg: (1,4);(5,7);(8,10);(13,18) 

Input interval – (3,7) 
Result : (1,7);(8,10);(13,18) 

Input Interval – (1,3) 
Result: (1,4);(5,7);(8,10);(13,18) 

Input interval – (11,12) 
Result: (1,4);(5,7);(8,10);(11,12);(13,18)

Inserting an interval in a sorted list of disjoint intervals，这里没有有效的答案

来源

2013-01-22 Peter

你是否假设你的初始间隔被排序？如果是这样，怎么样？ – Dan

你的问题是什么？ –

排序为，它们是不相交的，在数字行之前出现的间隔是 – Peter

你的问题和例子暗示非重叠的时间间隔。在这种情况下，您只需执行binary search - 无论是通过开始时间进行比较还是结束时间对于非重叠间隔都无关紧要，并且可以在找到的位置插入新间隔（如果尚未存在）。

UPDATE

我错过了在第一个例子中产生的合并。一个不好的情况是将一个较大的时间间隔插入一长串短时间间隔中，其中长时间间隔与很多短时间间隔重叠。为了避免线性搜索所有必须合并的间隔，可以执行两个二进制搜索 - 左起一个比较开始时间，右起一个比较结束时间。

现在，确定间隔是否存在，必须插入或必须与两次搜索找到的位置之间的间隔合并在一起是微不足道的。虽然这不是很复杂，但它可能非常容易出现off-by-one errors，并且需要进行一些测试。

来源

2013-01-22 17:40:53

如第一个例子所示，您可能还必须合并间隔。无论如何，如果原始插播已排序，它仍然是一个简单的任务;） – Dan

我想补充说，如果您的间隔与已经存在的间隔重叠，您可以在插入点合并间隔。 –

哦，错过了那个，谢谢！将解决答案。 –

将区间插入不相交的区间集合

回答

相关问题