Sum of intervals in Java

Question

I am stuck on this kata in CodeWars and I have tried for a long time, like for a week or so for one kata. If you want a description of my question, go here.

This is my code, if you believe me, there are lots of bugs in it. Can someone please help me out?

public static int sumIntervals(int[][] intervals) {
    int sum = 0;
    int[] currentLargeInterval = {intervals[0][0], intervals[0][0]};
    ArrayList<int[]> addedIntervals = new ArrayList<>();
    ArrayList<int[]> arrays = new ArrayList<>();
    addAll(arrays, intervals);
    ArrayList<int[]> removed = new ArrayList<>();
    for (int i = 0; i < arrays.size(); i++) {
        if (i > 0) {
            if (arrays.get(i - 1)[1] >= arrays.get(i)[0] && arrays.get(i - 1)[1] < arrays.get(i)[1]) {
                removed.add(arrays.get(i));
                currentLargeInterval[1] = arrays.get(i)[1];
            } else {
                addedIntervals.add(currentLargeInterval);
                currentLargeInterval = new int[]{arrays.get(i - 1)[0], arrays.get(i - 1)[0]};
            }
        }
    }
    addedIntervals.add(currentLargeInterval);
    arrays.removeAll(removed);
    arrays.addAll(addedIntervals);
    for (int[] a : arrays) {
        System.out.println(Arrays.toString(a));
    }
    return sum;
}

Answer 1

I think you are over-complicating the solution in general (which makes bugs harder to find), it seems that all that is really required is that you do not add duplicates in a Collection, and output the size of the collection afterward.

I whipped up a quick version of this (I only tried it out against 2 of the tests).

public static void main(String[] args) {
    int [][] intervals = {{1,5},{10, 20},{1, 6},{16, 19},{5, 11}};
    System.out.println(sumIntervals(intervals));
}

public static int sumIntervals(int [][] intervals) {
    ArrayList<Integer> values = new ArrayList<>();
    for (int [] row : intervals) {
        for (int k = row[0]; k < row[1]; k++) {
            if (!values.contains(k)) {
                values.add(k);
            }
        }
    }
    return values.size();
}

Output:

19

This solution first iterates against the outer array to obtain each range, then uses those values to iterate between them and add each number into a List if the number is not already in the List, by utilizing .contains().

Finally it returns the size of the List that contains each non-duplicated number.

Answer 2

I went and got this super fast answer using Intstream.

 public static int sumIntervals(int[][] intervals) {
        return intervals == null ? 0 : (int) Arrays.stream(intervals)
            .flatMapToInt(interval -> IntStream.range(interval[0], interval[1]))
            .distinct()
            .count();
    }

Answer 3

I came up with a slightly different solution using BitSet The principle is simple. Set the range of bits depicted by the specified ranges in the test suite. Overlaps are handled by the fact the some bits will be set multiple times within an already established range. The cardinality is the number of bits set which is also the sum of the ranges.

        BitSet b = new BitSet();
        for (int[] arr : list) {
            b.set(arr[0],arr[1]);
        }
        sum = b.cardinality();
        System.out.println(sum);

Answer 4

actually, the code @Nexevis provided will work but it can be faster just by using a set instead of an ArrayList.

    public static int sumIntervals(int [][] intervals) {
       if(intervals == null || intervals.length == 0) {
         return 0 ; 
       }
       Set<Integer> numsSet = new HashSet<>() ; 
       for (int [] row : intervals) {
           for (int k = row[0]; k < row[1]; k++) {
               if (!numsSet.contains(k)) {
                   numsSet.add(k);
               }
           }
       }
    return numsSet.size();
   }

since using Sets is generally faster than using Arrays or ArrayLists I think this would make your code faster as you requested.

I know that this is an old answer and you might have found it on your own but it's good to be here for all to see if somebody else encountered the same problem.

Answer 5

public static int sumIntervals(int[][] intervals) {
    // TODO: implement this method
    if (intervals == null || intervals.length == 0) return 0;
    int counter = 0;
    int[] start = new int[intervals.length];
    int[] end = new int[intervals.length];
    for (int[] interval : intervals){
        start[counter] = interval[0];
        end[counter] = interval[1];
        counter++;
    }
    counter = 0;
    for (int i = 0; i <= intervals.length - 1; i++)
        for (int j = i + 1; j < intervals.length; j++){
            if (start[j] >= start[i] && start[j] < end[i] && end[j] > end[i])
                start[j] = end[i]; //start of the second interval inside of the first interval 
            if (end[j] >= start[i] && end[j] < end[i] && start[j] < start[i])
                end[j] = start[i]; //end of the second interval inside of the first interval 
            if (start[j] >= start[i] && start[j] < end[i] && end[j] > start[i] && end[j] <= end[i])
                end[j] = start[j]; //whole the second interval inside of the first interval 
            if (start[j] <= start[i] && end[j] >= end[i])
                end[i] = start[i]; //whole the first interval inside of the second interval 
        }
    for (int i = 0; i < intervals.length; i++)
        counter += end[i] - start[i];
    return counter;
}