# How to Find the Sum of Intervals in Java

## 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
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},}));
}
}
```