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:
- Create a rating array and initialize all its elements with -1.
- For every price, fill the array with the maximum rating possible till that price.
- Continue till the maximum price/last element of rating array.
- Return rating[Y], because Y > X always.
My problem:
The above approach requires huge memory (atleast in C++) as the rating array will contain 10^9 elements (because price range is from 1 to 10^9). This is not possible because of memory constraints. We can probably use maps/dictionaries here, but then, they are heavy too. This is where I need some guidance.
My solution (C++) (SIGSEGV): But works fine with sample test cases. PS: I know this is the right solution, but array size is the problem here.
// This was already given
#define MAXSIZE 1000001
int solve()
{
//write code here
int rating[MAXSIZE];
fill(rating, rating+MAXSIZE, -1);
for (int i=0; i<N; i++)
rating[P[i]] = R[i];
int maxele = rating[0];
for (int i=0; i<MAXSIZE; i++)
{
rating[i] = max(maxele, rating[i]);
maxele = max(maxele, rating[i]);
}
return rating[Y];
}
My solution (Py3) (Using dict): Partially accepted (1/5 test cases - 20/100)
def Solve(N,Price,Rating,Q,Range):
# write your code here
# return a list of answers of Q queries
ans = {}
returnli = []
for i in range(len(Price)):
ans[Price[i]] = Rating[i]
for i in Range:
a = i[0]
b = i[1]
maxel = -1
for i in range(a, b+1):
if i in ans.keys():
maxel = max(maxel, ans[i])
if (i > max(ans.keys())):
break
returnli.append(maxel)
return returnli
I hope explaination given by me clears everything!!
