Determining the presence of an element in a given range

Question

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

 Length = B[i]-A[i] 

For instance:

 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 

The answer will 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:
The traditional approach . A simple loop of each element C in an array A , and if find in the range sets the values ​​of A[i] and B[i] to minus infinity or removes them (for Arraylist).

• Time complexity is a problem, so this is not a good approach.

HashTable : save the value in the hash table as A[i] as the key and B[i] as the value. Then find the item for the given C[i] and delete the key. I think this is not a very good approach.

Please provide me with an efficient algorithm for this.

Answer 1

So, based on your answer, we have no choice but to check each element of C on A and B. But since A and B are in increasing 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; 

Answer 2

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++; } } } 

I may have some error that I don't think about, but basically it means:

• Sort C. I know that you say you cannot do this, but I don’t understand why, if it is not a homework problem.
• Misses check for anything in ranges A, B if the number from C falls completely outside of these ranges. If the current number is greater than the largest number in ranges A, B (B [topRangeIndex]), return the current response counter, because no additional element from C (sorted) can again be in ranges A, B.
• Since C is sorted and the current number is larger than the bottom element in all ranges A, B, it starts to check whether the number is in C at the end B of each range A. The checked number is always the smallest element in C, so if it does not end B range A, this range A, B should never be checked again, so the lower case of RangeIndex is incremented.
• If each range was excluded by the while loop, we performed a check (the current element in C is greater than the largest number in any range A, B, we do not need to check anything.
• If the number in C that was checked was NOT greater than the number at the end of range A, B (located at the bottom of RangeIndex), that range A, B contains an element from C. We increase the response counter, move bottomRangeIndex up and continue.

Try this and see if it works. If this is homework and you really cannot sort C, you can change this to give the correct answer with a bit of tweaking, but I will not say how ...

Answer 3

This is a more efficient version using ArrayLists:

  int len = arrA.length; ArrayList<Integer> A = new ArrayList<Integer>(len); ArrayList<Integer> B = new ArrayList<Integer>(len); for (int i=0; i<len; i++) { A.add(arrA[i]); B.add(arrB[i]); } for (int i = 0; i < C.length; i++) { int c = C[i]; int j = 0; while (j<A.size() && A.get(j) <= c) { if (B.get(j) >= c) { A.remove(j); if (A.isEmpty()) return i+1; B.remove(j); } else { j++; } } } return 0; 

Answer 4

Here is one quick sketch for solving it in O (n log n). This may not be the best approach in practice, but simply intended for the n log n approach.

To summarize, this is a broad linear technique. Or rather, sweeping, in this case.

 1. Sort arrays A, B, and C (cost: n log n). Think of the arrays as queues (that is, "remove" elements from the left by increasing a start index). 2. Create current-intervals set (initially empty. Has O(log n) operations.) 2. While A not empty or B not empty or C not empty: 3. get the lowest element from the first (if any) elements in A, B, and C. 4. if it an A: 5. Add the corresponding interval to the current-intervals list 6. else if it a B: 7. Remove the corresponding interval from the current-intervals list 8. else it must be a C, so: 9. The answer to the query corresponding to C is the current-intervals list (in the current state) 

Answer 5

 for(int i =0 ;i<C.length;i++) for(int j=0;j<A.length;j++) { if(A[i]<=C[i] && B[i]>=C[i]) { answer++; A[i] = Integer.Max_Value; } } 

This will give the correct answer.

Answer 6

I experimented with some tree structures, but ended up returning to a simple binary search, so now it is O (nlogn):

 static int getAnswerV2a(int[] A, int[] B, int[] C) { int len = A.length; ArrayList<Interval> intervals = new ArrayList<Interval>(len); for (int i=0; i<len; i++) { intervals.add(new Interval(A[i], B[i])); } for (int i = 0; i < C.length; i++) { int c = C[i]; binarySearch(intervals, 0, intervals.size(), c); if (intervals.isEmpty()) return i+1; } return -1; } static class Interval { int start, end; Interval(int start, int end) { this.start = start; this.end = end; } boolean matches(int c) { return start <= c && c <= end; } } // Find an interval (between indices i and j) that matches c // When found, remove it from the List and adjust indices accordingly static void binarySearch(ArrayList<Interval> intervals, int i, int j, int c) { if (i==j) return; else if (i+1==j) { if (intervals.get(i).matches(c)) intervals.remove(i); } else { int mid = (int) Math.floor((i+j) / 2); Interval interval = intervals.get(mid); if (interval.start > c) binarySearch(intervals, i, mid, c); else if (interval.end < c) binarySearch(intervals, mid+1, j, c); else { intervals.remove(mid); binarySearch(intervals, i, j-1, c); } } }