What is wrong with this approach?

Правка en2, от abhi204, 2019-09-08 14:06:17

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. (I get Wrong Answer instead of TLE) Is there anything missing?

Теги maybegreedy, easy

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский abhi204 2019-09-08 14:06:17 35 Tiny change: 'le input. \nIs there' -> 'le input. (I get Wrong Answer instead of TLE)\nIs there'
en1 Английский abhi204 2019-09-03 21:59:00 1789 Initial revision (published)