Create Interval

Goal

Given 10,000 input range intervals (From to - To make the scenario worst, every 'from' is duplicated 50 times). The program takes one target value and displays all the ranges where the target belongs.

Example on 4 ranges:

Given the following ranges:

0 - 100
0 - 500
50 - 500
20 - 300

Target : 40

Output:

20 - 300
0 - 500
0 - 100

Explanation of the code below:

Every from value is mapped to an index++ starting from index = 0. So, in our example:

From => index
0 => 0
50 => 1
20 => 2

Now having an array of Tree Set called pointers, every index i of this array refers to the key of value 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 respectively by looking at the tree map 'key' => 'value' where value is the index of key in the pointers array.

Moreover, we want the to values added in the pointers array at every index to be sorted in a descending order (Later I explain why).

So now the pointer becomes like this:

index => TreeSet[values..]
0 => 500 | 100
1 => 500
2 => 300

Now we are ready to get the ranges where the target belongs to.

For target = 40

1 - Search for the closest floor key of 40 in the tree map. The program finds that 20 is the closest one.

2 - It goes to the index corresponding to 20 in the pointers array. To get the index of 20: look at the tree map at key 20. Index of 20 is 2.

3 - So go now to pointers[2], it finds that there is the number 300.

4 - Now the application checks if 300 is less than target, the reason it does this, is because I mentioned before that every Tree Set created is sorted in a descending order. So if 300 is smaller than the target, therefore no need to continue checking for the next values in the pointers[2] because it's guarantee that they are smaller.

5 - In this case, 300 is greater than target, then print the key as from and pointer[2] {current element} as to.

6 - Since only one element found in pointers[2], the for loop exits, and the key is removed from the tree map, so next time when the program wants to find the next closest floor key, it will find the next one, if it exists.

7 - (Next iteration of while loop) The next key found, after removing key 20, is 0, with index 0 according to the tree map.

8 - Go to pointers[0]. It finds that the number of elements in Tree Set at pointers[0] is 2.

9 - Start with the first element pointers[0] {first element}. Is 500 less than 40 ? No, print "range". Next element, is 100 less than 40 ? No, print "range". No more elements exit for loop.

10 - Remove key 0 from tree map.

11 - Now the While loop condition checks if there exist a closest floor key for the target. No, because 0 and 20 were removed. So condition not satisfied, exit while loop.

12 - Print time consumed, and end program :)

Hope you find the explanation useful.