totalCoveredLength.js

/*
          (2,4)
  (1,3) --------        (7,8)
  ----------           -------
  1    2   3   4  5 6  7    8

  total covered length = 4-1 + 8-7 = 4
*/
var assert = require('assert');

class Node {
  constructor(start, end) {
    this.start = start;
    this.end   = end;
  }

  static same(node1, node2) {
    return node1.start === node2.start && node1.start === node2.start;
  }

  static overlap(node1, node2) {
    if (Node.same(node1, node2)) {
      return node1;
    }

    if ((node2.start < node1.start) && (node1.start < node2.end) && (node2.end < node1.end)) {
      return new Node(node2.start, node1.end);
    } else if ((node1.start < node2.start) && (node2.start < node2.end) && (node2.end < node1.end)) {
      return node1;
    } else if ((node1.start < node2.start) && (node2.start < node1.end) && (node1.end < node2.end)) {
      return new Node(node1.start, node2.end);
    } else if ((node2.start < node1.start) && (node1.end < node2.end)) {
      return node2;
    }
    return null;
  }

  static comparator(node1, node2) {
    return node1.end > node2.end;
  }

  get length() {
    return this.end - this.start;
  }
}


class IntervalsCoverage {
  constructor() {
    this.nodes = []; // sorted array of Node
    this._length = 0;
  }

  addInterval(start, end) {
    var n = new Node(start, end);
    this.nodes.push(n);
    this.nodes.sort(Node.comparator);

    var l = 0;

    for (var i = 0; i < this.nodes.length; ) {

      var current = this.nodes[i];
      var j = i;

      while(j < this.nodes.length) {
        var isOverlap = Node.overlap(current, this.nodes[j]);
        if (isOverlap) {
          current = isOverlap;
          j++;
        } else {
          break;
        }
      }

      i = j;

      l += current.length;
    }

    // console.log("Current Length", l);
    this._length = l;
  }

  get length() {
    return this._length;
  }
}

var ic = new IntervalsCoverage();
ic.addInterval(1,3);
ic.addInterval(2,4);
ic.addInterval(7,8);
// should be 4
assert(ic.length === 4);

var ic = new IntervalsCoverage();
ic.addInterval(1,3);
ic.addInterval(2,4);
ic.addInterval(0,8);
// should be 8
assert(ic.length === 8);

var ic = new IntervalsCoverage();
ic.addInterval(1,3);
ic.addInterval(2,4);
ic.addInterval(10,200);
// should be 193
assert(ic.length === 193);