Two Tuple Search.

You are getting a number of two-tuple values <time, val>, where time is non-decreasing. Then a query asks for the value at a particular time. If a tuple exists for that time, it returns the val. Otherwise it returns val from the tuple that is the closest successor to the query time.e.g.
<1,3>, <8,6>, <10, 11>, <19, 4>, <23, 9>,...
Q = 6? Val = 6.
Q = 10? Val = 11.


Approach:
1. Store the tuple values in the map H as H<time, val>
2. remember the last tuple time in lastTime variable.
3. whenever the new tuple <time, value> comes store in another hashMap M where key is auto-increment id and value is interval object(lasttime+1, currenttime)
4. Now whenever we want to query, if the  Q=6 is not in the hashmap, then we do a binary search on the intervals to check in which interval Q lies and then return the value corresponding to currentTime.


For the above input M looks like:
key    value (lastTimestamp+1, currentTimestamp)
1 = (1,1)
2 = (2,8)
3 = (9,10)
4 = (11,19)
5 = (20, 23)


Lets see how we will Query for Q=6;
since Q=6 search in map H will return null;
So now we will do binary search for Q=6 in all the keys of map M
so we will get the result of binary search as:
2 = (2,8) : 6 belongs in the range of 2,8
now lets search for currentTimestamp ie 8 in map H, which will return value as 6.


code input/output:
5
1 3
8 6
10 11
19 4
23 9
value for time 6: 6
value for time 12: 4
value for time 10: 11