Sum of Intervals

Description:

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]
] );// => 9sumIntervals( [
   [1,4],
   [7, 10],
   [3, 5]
] );// => 7sumIntervals( [
   [1,5],
   [10, 20],
   [1, 6],
   [16, 19],
   [5, 11]
] );// => 19

My solution:

function sumIntervals(intervals){

  for(i=0;i<intervals.length;i++) {
    let min = intervals[i];
    let index;
    for(j=i;j<intervals.length;j++) {
      if(min[0] > intervals[j][0]) {
        min = intervals[j];
        index = j;
      }
    }
    intervals[index] = intervals[i];
    intervals[i] = min;
  }

  for(i=0;i<intervals.length-1;i+=0) {
    if(intervals[i][1] <= intervals[i+1][0]) {
      i++;
      continue;
    } else {
      intervals[i+1][0] = (intervals[i][0] <= intervals[i+1][0]) ? intervals[i][0] : intervals[i+1][0];
      intervals[i+1][1] = (intervals[i][1] >= intervals[i+1][1]) ? intervals[i][1] : intervals[i+1][1];
      intervals.splice(i,1);
    }
  }

  const sum = intervals.reduce(function(acc,cur){
    acc += cur[1] - cur[0];
    return acc;
  },0);

  return sum;
}

Best solutions:

function sumIntervals(intervals) {
  const ranges = new Set();

  intervals.forEach(([start, end]) => {
    for (let i = start; i < end; i++) ranges.add(i);
  });

  return ranges.size;
}

• Set() ES6에 추가된 것으로, 집합을 의미한다. 집합이기 때문에, 배열과 달리 같은 원소를 여러번 추가할 수 없다.
  
• Set.add() 객체의 맨 뒤에 값을 추가한다.
  

    const set1 = new Set();
    
    set1.add(42);
    set1.add(42);
    set1.add(13);
    
    for (const item of set1) {
      console.log(item);
      // expected output: 42
      // expected output: 13
    }

전체적인 과정은 다음과 같다.

각 인터벌에 대하여서 시작값과 끝나는 값까지 숫자를 ranges 라는 집합에 추가한다. 집합이기 때문에, 겹치는 것은 자동으로 여러개 추가되지 않는다. 결국 ranges 에 포함된 원소들의 수가 총 길이가 된다.

function sumIntervals(intervals){
  var numbers = [];
  intervals.forEach( function(interval) {
    for (var i = interval[0] ; i < interval[1] ; i++) {
      if (numbers.indexOf(i) == -1) numbers.push(i);
    }
  });
  return numbers.length;
}

똑같은 로직인데, 배열을 이용한 경우.