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[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:

 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<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:

 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[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

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