Dealing with overlapping numbers in an array

Question

My program takes a pair of numbers and subtracts them from one another then adds all the differences from the pairs back up for a total.

My problem is that some of the numbers overlap, by numbers I am using start and end times. I need to find a way to disregard overlapping numbers so that an input of

{{10, 14}, {4, 18}, {19, 20}, {19, 20}, {13, 20}

returns a total of 16 and not 27. Thus far I have created another array called hours to check off times already existing. Here is that portion of code:

public static int monitoring(int[][] intervals) {
    int sum = 0;
    int start = 0;
    int end = 0;
    boolean[] hours = new boolean[24];
    int count = 0;

    for(int i = 0; i < intervals.length; i++) {
        end = intervals[i][1];
        start = intervals[i][0];    
        for(int j = start; j < end; j++) {
            hours[j] = true;
            count++;
        sum += end - start;
        }
    }

    return sum;

Explain what you mean by "overlapping numbers" as it is unclear what is meant by that. — thermite, Mar 13 '15 at 18:12
No, it seems that this is the number of hours in a day covered by the union of the intervals. — RealSkeptic, Mar 13 '15 at 18:22
By overlapping, I mean for example {10,14} and {4,18} are overlapping since {4,18} would cover {10,14}. 4,5,6,7,8,9,10,11,12,13,14,15,16,17,18. — Robert, Mar 13 '15 at 18:35

Dae · Accepted Answer · 2015-03-13T18:30:00.030

2

I do not know what you are reaaly trying to get, 2 options possible:

you are probably trying to get difference between maximum of the 2nd element if pairs, and minimum of the 1st element in pairs
you want to count numbers of unique "points" (or hours) in given interval list.

Simplest solution can be:

            if (!hours[j]) {
                hours[j] = true;
                count++;
            }

In this case you do not even need "sum" variable.

edited Mar 13 '15 at 18:30

answered Mar 13 '15 at 18:19

Dae

67
4

I suggest a revision in your answer. Think of the case `{{4,8},{14,16}}`. I believe the OP wants the result to be 6, which is not `16-4`. Your code will give the correct result, but your text is a bit misleading. – RealSkeptic Mar 13 '15 at 18:25
Thank you all for your suggestions. I found adding another for loop such as: for(int x = 0; x < hours.length; x++){ if(hours[x]){ sum++; } } takes care of the problem. – Robert Mar 13 '15 at 20:58

Dealing with overlapping numbers in an array

1 Answers1