Trying to optimize the process of splitting overlapped intervals and merging duplicates. A unique condition in this scenario: if a merged interval starts where an original one ends, it is incremented by 1; if it ends where an original starts, it is decremented by 1. Sample data and expected result provided:
interface Interval {
start: number;
end: number;
type: Array<number>;
}
// initial 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);
// split and merge logic here
// expected resulting array
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] },
];
An existing solution uses nested loops but lacks efficiency. Any improvements welcome. Here's the current approach:
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 matches expected result
console.log(result);