拆分重叠间隔的更有效方法，然后合并重复项
More Efficient method to split overlapped intervals, then merge duplicates
所以我想找出最有效的方法来拆分重叠的间隔，然后合并重复项。针对我的情况的两个特定条件是，如果合并间隔的开始是原始间隔的结束，则它递增 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 的一个区间。这消除了 class 的边缘情况。因此，给定一个 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;
}
}
}
此算法是一种二分查找算法，如果您碰巧已经了解分区中正确间隔的位置，则可以为它提供有关开始和结束索引的提示。如果分区的长度那么这个算法应该是 ( ).
另一个有用的操作是在特定的 position 处拆分 partition。如果分区已经包含从该位置开始的区间，则您无需执行任何操作。否则需要找到跨越该位置的区间，将其一分为二：
// 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 数组），将每个间隔合并到其中，然后 return 最后的 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()，因此在最坏的情况下最终将成为 (²)。我认为这可能是你能为算法做的最好的事情了；这意味着你不应该需要三个嵌套循环，但如果你能避免有两个，我会感到惊讶。
您可以验证它产生的输出与您的版本相同。可能存在边缘情况，但我对在 Partition 上运行的算法更有信心，因为我不必一直问 "what if the position I'm looking at doesn't have an interval associated with it"？
备注：
您可能要考虑像 [start, end) 那样将间隔设为半开。即start应该是区间包含的最小位置，end应该是比区间大的最小位置。半开区间更容易组合和推理。 [start, end) 的长度是 end - start。如果您加入区间 [a, b) 和 [b, c)，您将得到 [a, c)。如果您决定需要从整数位置切换到分数位置，则半开间隔不需要更改任何代码。相反，闭区间需要仔细的数学运算才能在正确的位置添加或减去 1（或任何步长），因此容易出现 fence-post 错误。
正如我之前所说，性能通常很重要，但可能不如正确性重要。准确了解性能在您的案例中有多重要的唯一方法是针对负载对其进行测试并查看其表现如何。通常情况下，一个简单的算法比一个更快一点的复杂算法更可取，特别是如果你以后必须维护 and/or 调试代码。
好的，希望对你有帮助；祝你好运！
所以我想找出最有效的方法来拆分重叠的间隔，然后合并重复项。针对我的情况的两个特定条件是，如果合并间隔的开始是原始间隔的结束，则它递增 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 的一个区间。这消除了 class 的边缘情况。因此，给定一个 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;
}
}
}
此算法是一种二分查找算法，如果您碰巧已经了解分区中正确间隔的位置，则可以为它提供有关开始和结束索引的提示。如果分区的长度那么这个算法应该是 ( ).
另一个有用的操作是在特定的 position 处拆分 partition。如果分区已经包含从该位置开始的区间，则您无需执行任何操作。否则需要找到跨越该位置的区间，将其一分为二：
// 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 数组），将每个间隔合并到其中，然后 return 最后的 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()，因此在最坏的情况下最终将成为 (²)。我认为这可能是你能为算法做的最好的事情了；这意味着你不应该需要三个嵌套循环，但如果你能避免有两个，我会感到惊讶。
您可以验证它产生的输出与您的版本相同。可能存在边缘情况，但我对在 Partition 上运行的算法更有信心，因为我不必一直问 "what if the position I'm looking at doesn't have an interval associated with it"？
备注：
您可能要考虑像
[start, end)那样将间隔设为半开。即start应该是区间包含的最小位置，end应该是比区间大的最小位置。半开区间更容易组合和推理。[start, end)的长度是end - start。如果您加入区间[a, b)和[b, c)，您将得到[a, c)。如果您决定需要从整数位置切换到分数位置，则半开间隔不需要更改任何代码。相反，闭区间需要仔细的数学运算才能在正确的位置添加或减去1（或任何步长），因此容易出现 fence-post 错误。正如我之前所说，性能通常很重要，但可能不如正确性重要。准确了解性能在您的案例中有多重要的唯一方法是针对负载对其进行测试并查看其表现如何。通常情况下，一个简单的算法比一个更快一点的复杂算法更可取，特别是如果你以后必须维护 and/or 调试代码。
好的，希望对你有帮助；祝你好运！