Count total of number array with ignoring overlap number-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

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)

CodePudding user response：

Here's my version:

const getCoverage = arr => arr
  .reduce((result, el) => {
    if (!result.length) { 
      return [el];
    }
    let running = true, i = 0;
    while(running && i < result.length) {
      if (el.some(n => n >= result[i][0] && n <= result[i][1])) {
        result[i] = [Math.min(el[0], result[i][0]), Math.max(el[1], result[i][1])];
        running = false;
      } 
      i  ;
    }
    if (running) {
      result.push(el);
    }
    return result;
  }, [])
  .reduce((result, el) => el[1] - el[0]   result, 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.