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;
}
똑같은 로직인데, 배열을 이용한 경우.
Author And Source
이 문제에 관하여(Sum of Intervals), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gtfo/Sum-of-Intervals저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)