見習村29 - Sum of Intervals

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
2
3
4
5
[
   [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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

1
2
3
def sum_of_intervals(intervals)
  #return
end

Sample Testing

1
2
3
4
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

1
2
3
function sumIntervals(intervals){
  //TODO
}

Sample Testing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 才是對的

https://ithelp.ithome.com.tw/upload/images/20201014/20120826VfGTyC0IFD.jpg
圖片來源：Unsplash Vishal Shanto

Hint & Reference

Solution

Ruby

1
2
3
4
5
6
7
8
9
# 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

1
2
3
4
5
6
7
8
9
10
// 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;
}