因此，我试图找出最有效的方法来分割重叠的间隔，然后合并重复项。针对我的情况的两个特定条件是，如果合并间隔的开始是原始间隔的结束，则将其递增1。如果合并间隔的结束是原始间隔的开始，则将其递减1。这是一些示例数据，以及预期的结果：
interface Interval {
start: number;
end: number;
type: Array<number>;
}
// starting data
const arr: Array<Interval> = [
{ start: 0, end: 16, type: [42] },
{ start: 6, end: 30, type: [95] },
{ start: 11, end: 24, type: [126] },
{ start: 32, end: 47, type: [42] }
].sort((a, b) => a.start - b.start);
// magic splitting code here
// what we expect to end up with
const end_arr: Array<Interval> = [
{ start: 0, end: 5, type: [42] },
{ start: 6, end: 10, type: [42, 95] },
{ start: 11, end: 16, type: [42, 95, 126] },
{ start: 17, end: 24, type: [95, 126] },
{ start: 25, end: 30, type: [95] },
{ start: 32, end: 47, type: [42] },
];
我从技术上已经得到了答案，但是效率不是很高-涉及3个嵌套的for / forEach循环。当然有更有效的方法吗？这是该代码：
let startIndexArray: Array<number> = [];
let endIndexArray: Array<number> = [];
for (let i = 0; i < arr.length; i++) {
startIndexArray.push(arr[i].start);
endIndexArray.push(arr[i].end);
}
startIndexArray = startIndexArray.sort((a, b) => a - b);
endIndexArray = endIndexArray.sort((a, b) => a - b);
const indexArray = [...startIndexArray, ...endIndexArray].sort((a, b) => a - b);
const result: Array<Interval> = [];
arr.forEach((currentInterval) => {
for (let i = currentInterval.start; i < currentInterval.end; i++) {
if (indexArray.includes(i)) {
const position = indexArray.indexOf(i);
if (position !== indexArray.length - 1) {
let start = i;
let next = indexArray[position + 1];
if (endIndexArray.includes(start)) {
start = start + 1;
}
if (startIndexArray.includes(next)) {
next = next - 1;
}
let in_result = false;
result.forEach((mergedInterval) => {
if (mergedInterval.start === start && mergedInterval.end === next) {
mergedInterval.type = [...mergedInterval.type, ...currentInterval.type];
in_result = true;
}
});
if (!in_result) {
result.push({ start: start, end: next, type: [...currentInterval.type]});
}
}
}
}
});
// output is my expected, correct outcome
console.log(result);
以下算法是我能想到的最干净的算法，它具有合理的性能。我希望，使用您提供的特定示例数组，此代码和上面提供的代码将具有相似的性能水平，但是如果您开始使用更大的数组，那么与您的数组相比，您会看到性能提高。没有一套测试用例，很难确定。
无论如何，总体思路是这样的。让我们将Partition称为不重叠间隔的排序数组，该数组覆盖从-Infinity到Infinity的所有整数。
type Partition = Array<Interval>;
如果我们具有类型为partition的值Partition，我们知道partition[0].start === -Infinity，partition[partition.length-1].end === Infinity，并且对于任何索引i < partition.length - 1，partition[i].end + 1 === partition[i+1].start。
关于分区的一件好事是，它将始终只包含一个覆盖任何给定position的间隔。这样就消除了一类边缘情况。因此，给定一个partition: Partition和一个position: number，让我们找到包含它的partition内部间隔的索引：
// binary search of the partition to find the index of the interval containing position
// startIndex is a hint, where partition[startIndex].start <= position
// endIndex is a hint, where partition[startIndex].end > position
function findIndex(
partition: Partition,
position: number,
startIndex: number = 0,
endIndex: number = partition.length
) {
while (true) {
let i = (startIndex + endIndex) >> 1;
let cur = partition[i];
if (cur.end <= position) {
startIndex = i;
} else if (cur.start > position) {
endIndex = i;
} else {
return i;
}
}
}
此算法是一个二进制搜索，如果您碰巧已经知道了正确间隔可能在分区中的什么位置，它可以为您提供有关开始和结束索引的提示。如果分区的长度为𝑛，则此算法应为𝖮（𝗅𝗈𝗀）。
另一个有用的操作是在特定的partition处分割position。如果分区已经包含从该位置开始的间隔，则无需执行任何操作。否则，您需要找到跨越位置的间隔并将其分成两个部分：
// ensure that the partition contains an interval starting at position
// startIndex is a hint, where partition[startIndex].start <= position
// return the index of the interval starting at position
function splitAt(partition: Partition, position: number, startIndex: number = 0) {
let i = findIndex(partition, position, startIndex);
let cur = partition[i];
if (cur.start < position) {
partition.splice(i, 1,
{ start: cur.start, end: position - 1, type: cur.type.slice() },
{ start: position, end: cur.end, type: cur.type }
)
i++;
}
return i;
}
此算法使用findIndex()，因此也应为𝖮（𝗅𝗈𝗀）。 （编辑...我想这取决于splice()，所以可能只是𝖮（𝑛））。
给出partition: Partition和interval: Interval，如何将间隔合并到分区中？我们需要在区间的start位置和区间end位置之后分割分区，然后遍历受影响的区间，并向其中添加新区间的type数组：
// merge interval into partition
function merge(partition: Partition, interval: Interval) {
// split partition at interval's start, get index of starting interval in partition
let startIndex = splitAt(partition, interval.start);
// split partition at interval's end, get index of interval after ending interval
let endIndex = splitAt(partition, interval.end + 1, startIndex);
// add types to each interval between start and end
for (let i = startIndex; i < endIndex; i++) {
partition[i].type.push(...interval.type);
}
}
这是一对二进制搜索，以及对受影响间隔的遍历。在最坏的情况下，分区中的每个间隔都需要修改，因此应为𝖮（𝑛）。
最后，我们要做的就是将任意间隔的数组转换为您想要的格式，就是从一个空的Partition开始（该间隔从-Infinity到Infinity恰好有一个间隔，并且以一个空type数组），将每个间隔合并到其中，然后返回最终的Partition 没有type数组为空的任何间隔。这将自动抑制触摸Infinity或-Infinity的物体以及中间的任何孔：
// denormalize array into non-overlapping intervals
function denormalize(arr: Array<Interval>) {
// empty partition
const partition: Partition = [{ start: -Infinity, end: Infinity, type: [] }];
arr.forEach(interval => merge(partition, interval));
// turn partition into normal array by removing "empty" intervals
return partition.filter(i => i.type.length !== 0);
}
由于每个间隔运行merge()，在最坏的情况下，最终将变成this（𝖮²）。我认为这可能是该算法可以做的最好的事情。这意味着您不需要三个嵌套循环，但是如果您可以避免两个嵌套循环，我会感到惊讶。
您可以验证它产生与您的版本相同的输出。可能存在边缘情况，但是我对在Partition上运行的算法更有信心，因为我不必一直问“我正在查看的位置是否没有与之相关的间隔” ？
注意：
您可能想像在[start, end)中那样将间隔设为半开。也就是说，start应该是间隔中包含的最小位置，并且end应该是间隔中最小的位置[[greater。半开间隔很容易构成和推理。 [start, end)的长度为end - start。如果加入间隔[a, b)和[b, c)，则得到[a, c)。如果您决定需要从整数位置切换到小数，则半开间隔不需要任何代码更改。相反，封闭的间隔需要仔细的数学运算才能在正确的位置加上或减去1（或任何步长），因此很容易出现围栏错误。