在乔达时间优化许多间隔

我有一堆乔达时间Interval存储在列表中的对象。所有这些间隔都有有效的开始和结束时刻。这些间隔可以有任何重叠，邻接甚至间隙。在乔达时间优化许多间隔

我想将这些间隔平放（优化）到最大可能。我的意思是，我必须生成其他Interval对象，这些对象将代表从信息到信息，但没有冗余。

例如：

I1：2012-01-12T05：00：00.000/2013-03-18T14：00：00.000

I2：2012-04-12T04：00：00.000/2013- 02-10T06：00：00.000

I3：2015-12-12T04：00：00.000/2016-12-12T06：00：00.000

应该产生：

I1_o：2012-01-12T05 ：00：00.000/2013-03-18T14：00：00.000

I2_o：2015-12-12T04：00：00.000/2016-12-12T06：00：00.000

（I2是绝对内I1，所以可以忽略不计，并且所得到的2具有间隙）。

我知道Interval类中的三种方法可以帮助我，但我想我需要一个更通用的算法，可以搜索某种间隔之间的重叠，比如普通数字等。在此先感谢！

来源

2011-11-21 gyorgyabraham

按开始时间对间隔进行排序，并在间隔中循环。如果间隔的起始时间小于或等于间隔i-1的结束时间，则可以将它们合并为一个间隔，其结束时间是两个原始间隔的最大结束时间。（把所得到的间隔成一个新的列表，这样就可以通过原区间的排序列表，而无需修改安全地循环。）

来源

2011-11-21 13:06:15

谢谢，这是一个伟大的核心步骤！稍作修改：您必须检查i和i-1的开始时间，并将早期时间用作结果的开始时间。此外，结果间隔可能需要“重新优化”，因此您提到的核心步骤也可能必须在结果上执行。最后，这一步应该处理独立的时间间隔，它不会与其他时间间隔共享任何时间。无论如何，你的回答给了我这个想法，谢谢！ – gyorgyabraham

@gyabraham：对;我可能会更精确（但很明显，你有这个想法） - 你总是跟踪你正在建立的当前间隔，并且总是比较间隔_i_和当前间隔，并且合并间隔或设置_i_成为新的当前区间。 –

@gyabraham按开始时间对时间间隔进行排序意味着“一点点修复”是不必要的;先前排序的时间间隔具有较早的开始时间。 –

斯卡拉模式：

intervals.sortWith(_.start isAfter _.start).foldLeft(Seq[Interval]()) { 
    case (Nil, e) => Seq(e) 
    case (h :: t, e) if ((h gap e) == null) => 
    new Interval(e.interval.start, h.interval.end) +: t 
    case (a, e) => e +: a 
}

来源

2012-12-16 15:43:43 PTWithy

更通用的算法解释http://www.geeksforgeeks.org/merging-intervals/

来源

2015-07-23 09:52:35 electron

seq.sortWith(_.getStart isAfter _.getStart).foldLeft(Seq[Interval]()) { 
    case (Nil, e) => Seq(e) 
    case (h :: t, e) if (h gap e) == null => 
    val ins = if (h.contains(e)) { 
     h 
    } else if (e.contains(h)) { 
     e 
    } else { 
     new Interval(e.getStart, h.getEnd) 
    } 
    ins +: t 
    case (a, e) => e +: a 
}

来源

2016-06-10 20:30:55

虽然这段代码可能回答这个问题，但提供关于为什么和/或代码如何回答这个问题的附加上下文会提高它的长期价值。 – Ajean

在乔达时间优化许多间隔

回答

相关问题