将区间插入到不相交的区间集中

Question

给定排序的不相交集合(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，这里没有有效的答案

Answer 1

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

更新

我错过了第一个示例中发生的合并。一种糟糕的情况是将一个大间隔插入到短间隔的长列表中，其中长间隔与许多短间隔重叠。为了避免对必须合并的所有间隔进行线性搜索，可以执行两个二进制搜索-一个从左开始比较开始时间，另一个从右比较结束时间。

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