title: Optimize: Hackerearth Postman Software engineer intern question
body: <blockquote>
    <p>You want to buy a laptop. Each laptop has two parameters: Rating &amp; 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.</p>
    
    <p><strong>Input format:</strong></p>
    
    <p>The first line contains N denoting the number of inputs.</p>
    
    <p>The following N lines contain P &amp; R denoting price and range of a laptop.</p>
    
    <p>Next line contains Q denoting the number of queries.</p>
    
    <p>The following Q lines contain two integers X &amp; Y denoting the price range (inclusive).</p>
    
    <p><strong>Output format:</strong></p>
    
    <p>For each task Q, print the highest rating that can be bought within the range.</p>
    
    <p>If you cannot get any laptop within the range, print -1.</p>
    
    <p><strong>Constraints:</strong></p>
    
    <p>1 &lt;= N, Q &lt;= 10^6</p>
    
    <p>0 &lt;= R,P &lt;= 10^9</p>
    
    <p>1 &lt;= X &lt;= Y &lt;= 10^9 </p>
    
    <p>Time Limit: 6 Seconds for each input</p>
    
    <p><strong>Sample Input:</strong></p>
  
  <pre><code>5
  1000 300
  1100 400
  1300 200
  1700 500
  2000 600
  3
  1000 1400
  1700 1900
  0 2000
  </code></pre>
    
    <p><strong>Sample Output:</strong></p>
  
  <pre><code>400
  500
  600
  </code></pre>
  </blockquote>
  
  <p><strong>My Approach</strong></p>
  
  <ol>
  <li><p>Build a (Key, value) map</p></li>
  <li><p>while Y-- > X do,</p>
  
  <p>iterator = map.find(Y)</p>
  
  <p>if iterator, then, max_rating = max(max_rating, iterator.value)</p></li>
  <li><p>return max_rating</p></li>
  </ol>
  
  <p><strong><em>Here is my solution</em></strong></p>
  
  <pre><code>int solve(vector&lt;int&gt; P, vector&lt;int&gt; R, int X, int Y)
  {
        int max_value=-1;
        map&lt;int,int&gt; price_rating;
        for(int i=0;i&lt;N;i++)
        {
              price_rating.insert(pair&lt;int, int&gt;(P[i],R[i]));
        }
  
        while(y&gt;x)
        {
              auto iterator = price_rating.find(y);
              if(iterator!=price_rating.end())
              {
                     max_rating = max(max_rating,iterator-&gt;second);
              }
              y-=1;
        }
        return max_rating;
  }
  </code></pre>
  
  <p>Only a few test cases pass using the above solution while other test cases failed due to TLE (time limit exceeded). It would be great to know a better solution.</p>