Edited by:
- Much faster
- Much more efficient memory consumption.
- For 1000 inputs, this ensures that it works in less than 100 ms in the worst cases.
- For 10,000 input ranges, 10x is larger than the required input, it still works in less than 100ms for 50 duplicates
from ex: {0 - #} x50, {1 - #} x50, etc. for all from ranges.
goal
Given the 10,000 input interval intervals (From - To - To make the worst case scenario, each "of" is duplicated 50 times). The program takes one target value and displays all the ranges to which the target belongs.
An example of how it works for 4 ranges:
Given the following ranges:
0 - 100 0 - 500 50 - 500 20 - 300
Target: 40
Output
20 - 300 0 - 500 0 - 100
Algorithm explanation (using the previous example):
Each from value is mapped to index++ , starting at index = 0 . So in our example:
From => index 0 => 0 50 => 1 20 => 2
Now, having an array of tree sets called pointers , each index i this array references the key values of i in the tree set. So, pointers[0] refers to 'from': 0, pointers[1] refers to 'from': 50, pointers[2] refers to 'from': 20.
Now we add the to values to each from value, looking at the map of the tree 'key' => 'value' , where value is the key index in the pointers array.
In addition, we want the to values to added to the pointers array at each index, which should be sorted in descending order (I will explain why later).
So now the pointer will look like this:
index => TreeSet[values..] 0 => 500 | 100 1 => 500 2 => 300
Now we are ready to get the ranges to which the target belongs.
For target = 40
1 - Find the closest 40 floor key on the tree map. The program believes that 20 is the closest.
2 - It falls into the index corresponding to 20 in the array of pointers. To get index 20: look at the tree map with key 20. Index 20 is 2.
3 - So, go to pointers[2] , he discovers that there is a number 300.
4 - Now the application checks that 300 is less than the target, the reason why it does this is because I already mentioned that each created set of trees is sorted in descending order. Therefore, if the value 300 is less than the target, therefore, it is not necessary to continue checking the following values in pointers[2] , because they guarantee that they are less.
5 - In this case, 300 is larger than the target, then type the key as from and pointer[2] {current element} as to .
6 - Since only one element is found in pointers[2] , the for loop ends and the key is deleted from the tree map, so the next time the program wants to find the next closest floor key, it will find the next one if it exists.
7 - (Next iteration of the while loop) The next key found after deleting key 20 is 0, with index 0 according to the tree map.
8 - Go to pointers[0] . He finds that the number of elements in the tree set in pointers[0] is 2.
9 - Start with the first element pointers[0] {first element} . Is 500 less than 40? No, type "range." Next item, 100 is less than 40? No, type "range." There are no more items to loop.
10 - Remove key 0 from the tree map.
11 - Now the condition of the While loop checks if the closest key exists for the target. No, because 0 and 20 have been removed. Therefore, the condition is not met, exit the while loop.
12 - Printing time and final program :)
We hope you find a helpful explanation.
code
import java.util.Collections; import java.util.TreeMap; import java.util.TreeSet; public class Interval { public static void main(String[] args) { int MAX_SIZE = 10000; int[] from = new int[MAX_SIZE]; int[] to = new int[MAX_SIZE]; //Generate 10,000 (from - to), with 50 redundant (from range) for every value of from. (to make the application heavy) int c = 0; for(int i=0; i<MAX_SIZE;i++){ from[i] = 0+c; to[i] = from[i] + (int)(Math.random()*100); if(i%50 == 0) c++; } //Start time counting long time = System.currentTimeMillis(); int target = 97; TreeMap<Integer, Integer> treePointer = new TreeMap<Integer, Integer>(); // will sotre <From, index++> int index = 0; int size = from.length; TreeSet<Integer>[] pointers = new TreeSet[size]; //Array of tree set to store values of every "from" range //insert into tree for(int i=0; i<from.length;i++){ if(!treePointer.containsKey(from[i])){ //if the "from" does not exist in the tree yet, insert it treePointer.put(from[i], index); pointers[index++] = new TreeSet<Integer>(Collections.reverseOrder()); //sort descending order } //index of "from" in the pointers array int virtualIndex = treePointer.get(from[i]); //add the 'to' element to the corresponding index of "from" in Tree Set at pointers[index of "from"] pointers[virtualIndex].add(to[i]); } // Display part of the pointers array to understand how elements are stored // for(int i=0; i<10; i++){ // for(int current : pointers[i]){ // System.out.print(current + " "); // } // System.out.println(); // } //Start checking for the ranges Integer currentKey = -1; //dummy number at first while((currentKey = treePointer.floorKey(target)) != null){ // while there is a closest floor key //get index assigned to the closest floor key int virtualIndex = treePointer.get(currentKey); //loop on the elements found at pointers[index of closest floor number] for(int toValue : pointers[virtualIndex]){ if(toValue < target) //remember the values are sorted in a descending order, so whenever the value becomes smaller than the target don't continue the for loop break; System.out.println(currentKey + " - " + toValue); // else target less or equal to toValue, so print range } treePointer.remove(currentKey); //remove key from tree to fetch the next floor key in the next while iteration } //Display time consumed in ms System.out.println("\nTotal time: " + (System.currentTimeMillis() - time) + " ms"); } }