范围分裂问题

Question

乡亲,

很久以前就听说过这个问题.想发布它,以获得一些观点,如使用一些构造或其他有效的手段(专门的树木可能)

给出一组成对的范围(5,18)(12,23)(15,30)

将它们分成所有可能的子范围,这些子范围与集合中的其他范围重叠.喜欢(5,11)(12,14)(15,18)(19,23)(24,30)

谢谢大家,欣赏......

拉詹...

PS这是一个标准问题,如果是的话,想知道它的名字

Answer 1

将所有范围端点清除到列表中,但将它们标记为开始/结束点.

[(5, S), (18, E), (12, S), (23, E), (15, S), (30, E)]

按位置对它们进行排序,通过在终点之前放置起点来打破关系.

[(5, S), (12, S), (15, S), (18, E), (23, E), (30, E)]

然后,您可以通过遍历此列表来计算范围,跟踪到目前为止我们已经处理了多少个起始端点.如果我们看到一个起点,那就是输出新范围的开始.如果我们的计数是正数,我们必须首先结束当前范围.如果我们看到一个终点,则结束当前范围.