A和B。A中，这些区间按照它们的起始点排序。 A内的所有区间都不重叠。B中，这些区间按照它们的起始点排序。 B内的所有区间都不重叠。A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}
返回：
{[1,3], [7,8], [9,11]}
我在一次面试中遇到了这个问题，感到困惑。
我考虑比较两个列表之间的区间。如果两者之间有重叠部分，则将重叠部分添加到结果列表中。然后我推进具有较小起始间隔的列表的指针，但是直到面试结束都无法得出可行的解决方案。
解决这个问题的最佳方法是什么？
你有两个事件列表 - 进入时间间隔和离开时间间隔。合并这些列表，将当前状态保持为整数0、1、2（活动时间间隔计数）。
Get the next coordinate from both lists
If it is entering event
Increment state
If state becomes 2, start new output interval
If it is closing event
Decrement state
If state becomes 1, close current output interval
处理相等的关系（当值为[0..1]和[1..2]时），相应地选择规则 - 如果这些时间间隔不应该产生交集，则先处理关闭事件再处理打开事件。
这里有一个实现，遵循罗马的分治原则：
首先，找到一种方法，对于给定的两个区间，找到它们的重叠部分（如果有的话）。
/* Cases: A behind B, A overlap at start, A part of B, B part of A,
overlap at end, B starts after A ended:
A: 2..3..4..5
Bs: | |
0..1 | |
0..1..2..3 |
0..1..2..3..4..5..6
| 3..4 |
| 4..5..6
| | 6..7
*/
case class Interval (lower: Int, upper: Int) {
def overlap (other: Interval) : Option [Interval] = {
if (lower > other.upper || upper < other.lower) None else
Some (Interval (Math.max (lower, other.lower), Math.min (upper, other.upper)))
}
}
val a = List (Interval (0, 4), Interval (7, 12))
val b = List (Interval (1, 3), Interval (5, 8), Interval (9, 11))
天真的方法：气泡重叠（先让它工作，然后再让它快）：
scala> a.map (aa => b.map (bb => aa.overlap (bb))).flatten.flatten
res21: List[Interval] = List(Interval(1,3), Interval(7,8), Interval(9,11))
a.map (aa => b.map (bb => aa.overlap (bb)))
res19: List[List[Option[Interval]]] = List(List(Some(Interval(1,3)), None, None), List(None, Some(Interval(7,8)), Some(Interval(9,11))))
def findOverlaps (l1: List[Interval], l2: List[Interval]): List[Option[Interval]] = (l1, l2) match {
case (_, Nil) => Nil
case (Nil, _) => Nil
case (a :: as, b :: bs) => {
if (a.lower > b.upper) findOverlaps (l1, bs)
else if (a.upper < b.lower) findOverlaps (as, l2)
else if (a.upper > b.upper) a.overlap (b) :: findOverlaps (l1, bs)
else a.overlap (b) :: findOverlaps (as, l2)
}
}
前两行检查两个列表是否有一个为空，如果是，则不会有更多的重叠。
(a :: as, b :: bs) 是(l1, l2)的匹配，其中a是l1的头部，as是l1的尾部（可能是Nil），类似地，b是l2的头部，bs是l2的尾部。
如果a.lower > b.upper，则我们取b列表的尾部，并递归地使用整个l1列表和类似的方法处理整个l2列表，但只使用l1列表的尾部，如果b.lower > a.upper。
否则，我们应该有一个重叠，因此我们在任一情况下都要使用a.overlap(b)，其中一方是具有更高上限的整个列表，而另一方是其余列表。
scala> findOverlaps (a, b)
res0: List[Option[Interval]] = List(Some(Interval(1,3)), Some(Interval(7,8)), Some(Interval(9,11)))
A: {[7,12], [8,15], [9,16]}. B: {[5,8], [9,11], [10,15}, [11,17]}。返回：{[7,16]}？ - user9577088A：{[7,12]，[13,19]}。 B：{[5,8]，[9,11]，[12,15}，[16,18]}。 返回：{[7,18]}。 - user9577088 type Gap = (Int, Int)
/** The `merge`-step of a variant of merge-sort
* that works directly on compressed sequences of integers,
* where instead of individual integers, the sequence is
* represented by sorted, non-overlapping ranges of integers.
*/
def mergeIntervals(as: List[Gap], bs: List[Gap]): List[Gap] = {
require(!as.isEmpty, "as must be non-empty")
require(!bs.isEmpty, "bs must be non-empty")
// assuming that `as` and `bs` both are either lists with a single
// interval, or sorted lists that arise as output of
// this method, recursively merges them into a single list of
// gaps, merging all overlapping gaps.
@annotation.tailrec
def mergeRec(
gaps: List[Gap],
gapStart: Int,
gapEndAccum: Int,
as: List[Gap],
bs: List[Gap]
): List[Gap] = {
as match {
case Nil => {
bs match {
case Nil => (gapStart, gapEndAccum) :: gaps
case notEmpty => mergeRec(gaps, gapStart, gapEndAccum, bs, Nil)
}
}
case (a0, a1) :: at => {
if (a0 <= gapEndAccum) {
mergeRec(gaps, gapStart, gapEndAccum max a1, at, bs)
} else {
bs match {
case Nil => mergeRec((gapStart, gapEndAccum) :: gaps, a0, gapEndAccum max a1, at, bs)
case (b0, b1) :: bt => if (b0 <= gapEndAccum) {
mergeRec(gaps, gapStart, gapEndAccum max b1, as, bt)
} else {
if (a0 < b0) {
mergeRec((gapStart, gapEndAccum) :: gaps, a0, a1, at, bs)
} else {
mergeRec((gapStart, gapEndAccum) :: gaps, b0, b1, as, bt)
}
}
}
}
}
}
}
val (a0, a1) :: at = as
val (b0, b1) :: bt = bs
val reverseRes =
if (a0 < b0)
mergeRec(Nil, a0, a1, at, bs)
else
mergeRec(Nil, b0, b1, as, bt)
reverseRes.reverse
}