Finding if the element exist in a given range

Question

I have two arrays A and B. And I have to find the number of elements required by array C to fit into a specific length.

Length = B[i]-A[i]

For example:

A[0] = 1    B[0] = 4
A[1] = 4    B[1] = 5
A[2] = 5    B[2] = 9
A[3] = 8    B[3] = 10
and 
C[0] = 4
C[1] = 6
C[2] = 7
C[3] = 10
C[4] = 2

Answer would be 4.

Explanation:

C[0] is falling in the range of (A[0],B[0]) and (A[1],B[1])
C[1] is falling in the range of (A[2],B[2]) 
C[2] is of no use
C[3] is falling in the range of (A[3],B[3])
so the total is 4

My approaches:
Traditional approach: Simple looping every element of C in array A and if find in the range set the value of A[i] and B[i] to minus infinity or remove them(for Arraylist).

• Time complexity is an issue so not a good approach.

HashTable: Storing the value in hash table as A[i] as key and B[i] as value. Then finding the element for a given C[i] and removing the key. I think it is not a good approach

Please provide me a efficient algorithm for this.

Answer 1

If the input ranges are already ordered from smallest to largest (B[i] <= A[i+1]):

int bottomRangeIndex = 0;
int topRangeIndex = numberOfABRangesYouHave - 1;
int answerCounter = 0;

C.sort(); // Sort C so that it goes from smallest to largest number.

for number in C: {
    if (number < A[bottomRangeIndex]) {
        continue;
    } else if (number > B[topRangeIndex]) {
        return answerCounter;
    } else {
        while ((number > B[bottomRangeIndex++]) && (bottomRangeIndex <= topRangeIndex)) {
            // Just keeps incrementing bottomRangeIndex.
        }
        if (bottomRangeIndex > topRangeIndex) {
            return answerCounter;
        } else {
            answerCounter++;
            bottomRangeIndex++;
        }
    }
}

This might have some bug that I am not thinking of, but basically what this does is:

1. Sorts C. I know you say you can't do this, but I fail to see why unless it's a homework problem.
2. Skips checking anything in the A,B ranges if the number from C falls completely outside of those ranges. If the current number is greater than the biggest number in the A,B ranges (B[topRangeIndex]), return the current answer counter because no further element from C (sorted) could be in the A,B ranges again.
3. Since C is sorted and the current number is greater than the bottom element in all A,B ranges, starts checking if the number in C falls inside the B end of each A range. The number being checked is always the smallest element in C, so if it fails to fall within the B end of an A range, that A,B range should never be checked again so the bottomRangeIndex is incremented.
4. If every range has been eliminated by the while loop, we are done checking (the current element in C is greater than the biggest number in any A,B range, we do not need to check anything else.
5. If the number in C being checked was NOT greater than a number at the end of an A,B range (located at bottomRangeIndex), that A,B range contained an element from C. We increment the answer counter, move the bottomRangeIndex up, and continue.

Try this and see if it works. If this is homework and you really can't sort C, then you can modify this to give you the right answer with a small amount of tweaking, but I won't say how...

Answer 2

Ok so based on your answer, we have no choice but to check each element of C against A and B. But since A and B are in ascending order, performance should be reasonable:

    int len = A.length;
    boolean[] eliminated = new boolean[len]; // initially all elements are false
    int totalEliminated = 0;

    for (int i = 0; i < C.length; i++) {
        int c = C[i];
        for (int j = 0; j < len && A[j] <= c; j++) {
            if (B[j] >= c && !eliminated[j]) {
                System.out.println(c + " eliminates " + A[j] + " - " + B[j]);
                eliminated[j] = true;
                if (++totalEliminated == len) {
                    return i+1;
                }
            }
        }
    }
    return 0;