c++ - 优化: Hackerearth Postman Software engineer intern question

Question

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:

1 <= N, Q <= 10^6

0 <= R,P <= 10^9

1 <= X <= Y <= 10^9

Time Limit: 6 Seconds for each input

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

我的方法

1. 构建一个(键，值)映射

2. 而 Y--> X 做，

   迭代器 = map.find(Y)

   如果是迭代器，那么，max_rating = max(max_rating, iterator.value)

3. 返回 max_rating

这是我的解决方案

int solve(vector<int> P, vector<int> R, int X, int Y)
{
      int max_value=-1;
      map<int,int> price_rating;
      for(int i=0;i<N;i++)
      {
            price_rating.insert(pair<int, int>(P[i],R[i]));
      }

      while(y>x)
      {
            auto iterator = price_rating.find(y);
            if(iterator!=price_rating.end())
            {
                   max_rating = max(max_rating,iterator->second);
            }
            y-=1;
      }
      return max_rating;
}

使用上述解决方案只有少数测试用例通过，而其他测试用例由于 TLE(超出时间限制)而失败。知道更好的解决方案会很棒。

Answer 1

查看Segment tree .

我们的想法是首先构建一个线段树，其中每个节点代表一个价格范围并存储该范围内的最高评分。

例如，如果您的数据有 7 个价格，{10, 20, 30, 40, 50, 60, 70}，您将创建一个包含这些节点的树:

                 [10-70]
                /        \
           [10-30]        [40-70]
          /      \         /      \
       [10-20]   [30]  [40-50]    [60-70]
       /   \            /   \      /   \
     [10]  [20]      [40]  [50]  [60]  [70]

叶子是只有一个价格的“范围”。您可以向上冒泡该树的最大评级，因此每个节点都将具有该特定范围的最大评级。

然后，对于实际查询，您可以沿着树向下走(深度优先搜索)，并且:

• 排除通过范围与查询范围不重叠的节点的路径
• 当存在部分重叠时继续进一步向下钻取(扩展路径)
• 在范围完全在查询范围内的节点处停止并回溯

最终您将到达加起来等于查询范围的节点。从递归回溯的同时从这些节点获得最大评分。

这将使查询在 O(logn) 中运行。