## 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 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 20 21 22 23 24 25 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 `````` ``````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)); int result = 0; int currentIntervalEnd = intervals; for (int[] interval : intervals) { int intervalStart = interval; int intervalEnd = interval; if (intervalEnd > currentIntervalEnd) { result += intervalEnd - Math.max(intervalStart, currentIntervalEnd); currentIntervalEnd = intervalEnd; } } return result; } } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````package cw; import java.util.*; public class Interval { final static private Comparator CMP_RNG = Comparator.comparingInt(rng -> rng); 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

Option 3:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````package cw; import java.util.Arrays; public class Interval { public static int sumIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(b, a)); return Arrays.stream(intervals) .mapToInt(ints -> { int[] temp = new int[]{ints, ints}; Arrays.fill(ints, Integer.MAX_VALUE); Arrays.stream(intervals).forEach(arr -> { if ((arr >= temp && arr <= temp) || (arr >= temp && arr <= temp)) { temp = Math.min(temp, arr); temp = Math.max(temp, arr); Arrays.fill(arr, Integer.MAX_VALUE); } }); return temp - temp; }).sum(); } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 `````` ``````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 public void shouldAddDisjoinedIntervals() { 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 public void shouldAddAdjacentIntervals() { assertEquals(54, sumIntervals(new int[][]{{1, 2}, {2, 6}, {6, 55}})); assertEquals(23, sumIntervals(new int[][]{{-2, -1}, {-1, 0}, {0, 21}})); } @Test public void shouldAddOverlappingIntervals() { 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},})); } } ``````