29 - Sum of Intervals

Don't say so much, just coding...

Instruction

Write a function called sumIntervals/sum_intervals() that accepts an array of intervals, and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.

Intervals
Intervals are represented by a pair of integers in the form of an array. The first value of the interval will always be less than the second value. Interval example: [1, 5] is an interval from 1 to 5. The length of this interval is 4.

Overlapping Intervals
List containing overlapping intervals:

  [
     [1,4],
     [7, 10],
     [3, 5]
  ]

The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap, we can treat the interval as [1, 5], which has a length of 4.

Examples:

  sumIntervals( [
     [1,2],
     [6, 10],
     [11, 15]
  ] ); // => 9
  
  sumIntervals( [
     [1,4],
     [7, 10],
     [3, 5]
  ] ); // => 7
  
  sumIntervals( [
     [1,5],
     [10, 20],
     [1, 6],
     [16, 19],
     [5, 11]
  ] ); // => 19

Ruby

Init

  def sum_of_intervals(intervals)
    #return
  end

Sample Testing

  Test.assert_equals(sum_of_intervals([[1, 5]]), 4)
  Test.assert_equals(sum_of_intervals([[1, 5], [6, 10]]), 8)
  Test.assert_equals(sum_of_intervals([[1, 5], [1, 5]]), 4)
  Test.assert_equals(sum_of_intervals([[1, 4], [7, 10], [3, 5]]), 7)

Javascript

Init

  function sumIntervals(intervals){
    //TODO
  }

Sample Testing

  describe('sumIntervals', function(){
    it('should return the correct sum for non overlapping intervals', function(){
      var test1 = [[1,5]];
      var test2 = [[1,5],[6,10]];
      Test.assertEquals(sumIntervals(test1), 4);
      Test.assertEquals(sumIntervals(test2), 8);
    });
    
    it('should return the correct sum for overlapping intervals', function(){
      var test1 = [[1,5],[1,5]];
      var test2 = [[1,4],[7, 10],[3, 5]];
      Test.assertEquals(sumIntervals(test1), 4);
      Test.assertEquals(sumIntervals(test2), 7);
    });
  });

Thinking

想法(1): 第一个直觉都先 map 来处理，但原来发现有 flat_map 可以更清楚来做
想法(2): 注意要为 uniq 才是对的

图片来源：Unsplash Vishal Shanto

Hint & Reference

• Ruby
  • Ruby - apidock flat_map
• JavaScript
  • JS - MDN Array.prototype.forEach()
  • JS - MDN Object.keys()

Solution

Ruby

  # Solution 1
  def sum_of_intervals(intervals)
    intervals.map{ |a| (a[0]...a[1]).to_a }.flatten.uniq.size
  end
  
  # Solution 2
  def sum_of_intervals(intervals)
    intervals.flat_map { |x, y| [*x...y] }.uniq.size
  end

Javascript

  // Solution 1
  function sumIntervals(intervals){
    var numbers = {};
    intervals.forEach(function(x) {
      for (var i = x[0]; i < x[1]; i++) {
        numbers[i] = i;
      }
    });
    return Object.keys(numbers).length;
  }