I came across a seemingly easy problem recently which is as follows:

Problem:

You want to buy a laptop. Each laptop has two parameters: Rating & Price. Your task is to buy a laptop with the highest rating within a given price range. Given Q tasks, each query consisting of price range required, you have to print the highest rated laptop that can be bought within that price range.

Input format:

The first line contains N denoting the number of inputs. The following N lines contain P & R denoting price and range of a laptop. Next line contains Q denoting the number of queries. The following Q lines contain two integers X & Y denoting the price range (inclusive). Output format: For each task Q, print the highest rating that can be bought within the range. If you cannot get any laptop within the range, print -1.

Constraints:

Sample Input:

5

1000 300

1100 400

1300 200

1700 500

2000 600

3

1000 1400

1700 1900

0 2000

Sample Output:

400

500

600

My approach:

1- Create a Map of laptops having key=price & value=rating (C++ maps are already sorted in ascending order by keys)

2- initialize result=-1

3- Take the query range as input and find the first key which belongs to this range. (If none of the keys belong in this range, return result)

4- Starting from this key, iterate over the map and take result=max(result, current rating) (Iterate until either the current key exceeds the query range OR traversal over the map is complete)

5- Return result

My problem:

This approach fails for all inputs except the given sample input. Is there anything missing?