Methods to Discover the Sum of Intervals in Java

The problem

Write a perform known as sumIntervals/sum_intervals() that accepts an array of intervals, and returns the sum of all of the interval lengths. Overlapping intervals ought to solely be counted as soon as.

Intervals

Intervals are represented by a pair of integers within the type of an array. The primary worth of the interval will all the time be lower than the second worth. Interval instance: [1, 5] is an interval from 1 to five. The size of this interval is 4.

Overlapping Intervals

Checklist containing overlapping intervals:

[
   [1,4],
   [7, 10],
   [3, 5]
]

The sum of the lengths of those intervals is 7. Since [1, 4] and [3, 5] overlap, we are able to deal with the interval as [1, 5], which has a size 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

Assessments with massive intervals

Your algorithm ought to have the ability to deal with massive intervals. All examined intervals are subsets of the vary [-1000000000, 1000000000].

The answer in Java

Choice 1:

bundle cw;

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

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

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

Choice 2:

bundle cw;
import java.util.*;

public class Interval {

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

    public static int sumIntervals(int[][] intervals) {
        if (intervals==null) return 0;
        
        int     s      = 0,
                prime    = Integer.MIN_VALUE;
        int[][] ranges = Arrays.copyOf(intervals, intervals.size);
        Arrays.kind(ranges, CMP_RNG);
        
        for (int[] rng: ranges) {
            if (prime<rng[0])   prime = rng[0];
            if (prime<rng[1]) { s  += rng[1]-top; prime = rng[1]; }
        }
        return s;
    }
}

Choice 3:

bundle cw;

import java.util.Arrays;

public class Interval {

    public static int sumIntervals(int[][] intervals) {
        Arrays.kind(intervals, (a, b) -> Integer.examine(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();
    }
}

Check circumstances to validate our answer

import org.junit.Check;

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

public class IntervalTest {

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

	@Check
	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}}));
	}
  
  @Check
	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}}));
	}

	@Check
	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}}));
	}

	@Check
	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}}));
	}

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