## The challenge#

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

sumIntervals( [
[0, 20],
[-100000000, 10],
[30, 40]
] ) => 100000030
``````

Tests with large intervals

Your algorithm should be able to handle large intervals. All tested intervals are subsets of the range `[-1000000000, 1000000000]`.

## The solution in Java#

Option 1:

``````package cw;

import java.util.Arrays;
import java.util.Comparator;

public class Interval {
public static int sumIntervals(int[][] intervals) {
if (intervals == null || intervals.length < 1) {
return 0;
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int result = 0;
int currentIntervalEnd = intervals[0][0];

for (int[] interval : intervals) {
int intervalStart = interval[0];
int intervalEnd = interval[1];
if (intervalEnd > currentIntervalEnd) {
result += intervalEnd - Math.max(intervalStart, currentIntervalEnd);
currentIntervalEnd = intervalEnd;
}
}
return result;
}
}
``````

Option 2:

``````package cw;
import java.util.*;

public class Interval {

final static private Comparator<int[]> CMP_RNG = Comparator.<int[]>comparingInt(rng -> rng[0]);

public static int sumIntervals(int[][] intervals) {
if (intervals==null) return 0;

int     s      = 0,
top    = Integer.MIN_VALUE;
int[][] ranges = Arrays.copyOf(intervals, intervals.length);
Arrays.sort(ranges, CMP_RNG);

for (int[] rng: ranges) {
if (top<rng[0])   top = rng[0];
if (top<rng[1]) { s  += rng[1]-top; top = rng[1]; }
}
return s;
}
}
``````

Option 3:

``````package cw;

import java.util.Arrays;

public class Interval {

public static int sumIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(b[1], a[1]));
return Arrays.stream(intervals)
.mapToInt(ints -> {
int[] temp = new int[]{ints[0], ints[1]};
Arrays.fill(ints, Integer.MAX_VALUE);
Arrays.stream(intervals).forEach(arr -> {
if ((arr[0] >= temp[0] && arr[0] <= temp[1])
|| (arr[1] >= temp[0] && arr[1] <= temp[1])) {
temp[0] = Math.min(temp[0], arr[0]);
temp[1] = Math.max(temp[1], arr[1]);
Arrays.fill(arr, Integer.MAX_VALUE);
}
});
return temp[1] - temp[0];
}).sum();
}
}
``````

## Test cases to validate our solution#

``````import org.junit.Test;

import static cw.Interval.sumIntervals;
import static org.junit.Assert.assertEquals;

public class IntervalTest {

@Test
public void shouldHandleEmptyIntervals() {
assertEquals(0, sumIntervals(new int[][]{}));
assertEquals(0, sumIntervals(new int[][]{{4, 4}, {6, 6}, {8, 8}}));
}

@Test
assertEquals(9, sumIntervals(new int[][]{{1, 2}, {6, 10}, {11, 15}}));
assertEquals(11, sumIntervals(new int[][]{{4, 8}, {9, 10}, {15, 21}}));
assertEquals(7, sumIntervals(new int[][]{{-1, 4}, {-5, -3}}));
assertEquals(78, sumIntervals(new int[][]{{-245, -218}, {-194, -179}, {-155, -119}}));
}

@Test
public void shouldHandleLargeIntervals() {
assertEquals(2_000_000_000, sumIntervals(new int[][]{{-1_000_000_000, 1_000_000_000}}));
assertEquals(100_000_030, sumIntervals(new int[][]{{0, 20}, {-100_000_000, 10}, {30, 40}}));
}

@Test
assertEquals(54, sumIntervals(new int[][]{{1, 2}, {2, 6}, {6, 55}}));
assertEquals(23, sumIntervals(new int[][]{{-2, -1}, {-1, 0}, {0, 21}}));
}

@Test
assertEquals(7, sumIntervals(new int[][]{{1, 4}, {7, 10}, {3, 5}}));
assertEquals(6, sumIntervals(new int[][]{{5, 8}, {3, 6}, {1, 2}}));
assertEquals(19, sumIntervals(new int[][]{{1, 5}, {10, 20}, {1, 6}, {16, 19}, {5, 11}}));
}

@Test
public void shouldHandleMixedIntervals() {
assertEquals(13, sumIntervals(new int[][]{{2, 5}, {-1, 2}, {-40, -35}, {6, 8}}));
assertEquals(1234, sumIntervals(new int[][]{{-7, 8}, {-2, 10}, {5, 15}, {2000, 3150}, {-5400, -5338}}));
assertEquals(158, sumIntervals(new int[][]{{-101, 24}, {-35, 27}, {27, 53}, {-105, 20}, {-36, 26},}));
}

}
``````