查找两个int数组之间的重叠范围并拆分/插入它们

Question

有两个数组，每个数组总是包含偶数(但不等于(的整数，因此每对都将形成一个范围，例如1..5、8..12等。

var defaultArray: [Int] = [1, 5, 8, 12]
var priorityArray: [Int] = [1, 3, 5, 10, 13, 20]

我正在寻找的是一种通用算法，它将查找priorityArray的范围与defaultArray范围重叠的每次出现，并将priorityRange插入defaultArray，同时在必要时将默认范围拆分。

目标是具有范围的组合阵列，同时保持其原始的"范围"；"类型"；像这样：

var result: [Int] = [
1, 3,   // priority
3, 5,   // default
5, 10,  // priority
10, 12, // default
13, 20  // priority
]

我将使用一个简单的结构来说明最终想要的结果：

var result: [Range] = [
Range(from: 1, until: 3, key: "priority"),
Range(from: 3, until: 5, key: "default"),
Range(from: 5, until: 10, key: "priority"),
Range(from: 10, until: 12, key: "default"),
Range(from: 13, until: 20, key: "priority")
]

Answer 1

我们从这些数组def和prio开始，首先检查间隔本身是否根据其开始/结束点进行了排序。然后，这些数组将在第一个数组位置中包含最小的数字。确保这些数组简单/正确(=没有重叠的间隔(。如果不是，你可以对它们进行简化/消毒。

然后我们初始化

• 数组索引d=0以索引def数组
• 数组索引p=0以索引prio数组
• 一个新的数组CCD_ 7来保存所有新创建的区间
• 保持当前状态的变量s=none

我们现在确定CCD_ 9和CCD_。如果def[d]<prio[p]，我们设置t=def[d]，递增d，设置s=def。如果CCD_ 16>prio[p], we sett=prio[p]，递增p并设置s=prio。如果它们相等，我们设置t=prio[p]，递增p和d，并设置s=both。

现在，我们可以初始化result数组的一个新条目，start=def[0]。优先级是def(如果是s==def(或prio(如果s是prio或both(。要确定结束，您可以再次比较def[d]和prio[p]，以确定它应该在哪里结束。此时，您应该再次调整s，但要确保跟踪您所处的正确状态(根据def[d]和prio[p]之间的关系，从both到def、prio或none(。正如OP的评论中所提到的，不同的可能性可能需要更多的澄清，但你应该能够将它们纳入一个状态。

从那里开始，你可以不断迭代和调整你的变量，直到两者都完成(使用d=len(def)和p=len(prio)。你最终应该会得到一个包含所有所需合并区间的漂亮数组。

这基本上是对2个阵列的有状态扫描，跟踪整数范围内的当前位置，一次前进1个(可能是2个(位置。