0
231
ViewsCount total of number array with ignoring overlap number
I have this kind of problem and trying to solve it by using Javascript/Go. Given this array of number set, I would like to find the sum of number. The calculation should ignore the overlap and consider to count it as only once.
const nums = [[10, 26], [43, 60], [24,31], [40,50], [13, 19]]
It would be something like following if translated into the picture.
The result should 41
The rules are
- Overlap set of number (pink area) should be count once.
- Count total sum of green area.
- Total for both.
Any help will be appreciated.
3 answers
Answer question0
Here's an one-liner solution using javascript (Assuming the correct answer is 41 instead of 42).
The idea is to iterate all interval numbers and put them in a single array, then trim all the duplicates using Set. The time complexity is not optimal but it's short enough.
const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]];
const total = new Set(nums.reduce((acc, [from, to]) =>
[...acc, ...Array.from({ length: to - from }, (_, i) => i + from)], [])).size;
console.log(total);Not sure how to do it with go but it's just a proposal.
0
Here's my version:
const getCoverage = arr => arr
.reduce((results, el) => {
if (!results.length) {
return [el];
}
let running = true, i = 0;
while(running && i < results.length) {
if (el.some(n => n >= results[i][0] && n <= results[i][1])) {
results[i] = [
Math.min(el[0], results[i][0]),
Math.max(el[1], results[i][1])
];
running = false;
}
i++;
}
if (running) {
results.push(el);
}
return results;
}, [])
.reduce((total, el) => el[1] - el[0] + total, 0);
console.log(
getCoverage([[10, 26], [43, 60], [24,31], [40,50], [13, 19]])
);The first reducer merges overlapping (and adjacent) intervals and the second one adds up the diffs from the resulting merged ones.
0
You could sort the pairs and reduce by checking the second value and then add the deltas for getting the sum.
const
nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]],
result = nums
.sort((a, b) => a[0] - b[0] || a[1] - b[1])
.reduce((r, [...a]) => {
const last = r[r.length - 1];
if (last && last[1] >= a[0]) last[1] = Math.max(last[1], a[1]);
else r.push(a);
return r;
}, [])
.reduce((s, [l, r]) => s + r - l, 0);
console.log(result)