时间戳

首页 > 解决方案 > 优化：Hackerearth Postman 软件工程师实习生问题

c++ - 优化：Hackerearth Postman 软件工程师实习生问题

问题描述

你想买一台笔记本电脑。每台笔记本电脑都有两个参数：评级和价格。您的任务是购买给定价格范围内评级最高的笔记本电脑。给定 Q 任务，每个查询都包含所需的价格范围，您必须打印可以在该价格范围内购买的评价最高的笔记本电脑。

输入格式：

第一行包含 N 表示输入的数量。

以下 N 行包含 P&R，表示笔记本电脑的价格和范围。

下一行包含 Q 表示查询的数量。

以下 Q 行包含两个整数 X 和 Y，表示价格范围（含）。

输出格式：

对于每个任务 Q，打印在该范围内可以购买的最高评分。

如果您无法在该范围内获得任何笔记本电脑，请打印 -1。

约束：

1 <= N, Q <= 10^6

0 <= R,P <= 10^9

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

时间限制：每个输入 6 秒

样本输入：

5
1000 300
1100 400
1300 200
1700 500
2000 600
3
1000 1400
1700 1900
0 2000

样本输出：

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（超出时间限制）而失败。很高兴知道更好的解决方案。

标签： c++algorithmdictionaryoptimization

解决方案

查看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) 中运行。

推荐阅读