亚马逊上有 n 个供应商在特定时间以特定价格销售产品,我必须设计一个算法来选择特定时间价格最低的产品。
例如:对于下面的一组输入
输入格式:
<StartTime, EndTime, Price of product by this vendor in this time frame>
1 5 20
3 8 15
7 10 8
输出应该是:
1 2 20
3 6 15
7 10 8
我已经通过将与时间对应的价格存储在 hashmap 中来完成解决方案,如果存在价格低于与该时间对应的旧价格,则更新价格,然后在 vendor 类中创建列表以存储所有与特定价格相对应的时间。
但是上面的解决方案需要 O(n2) 的时间复杂度,所以寻找一些花哨的 DS 或方法来以较小的时间复杂度解决这个问题。
最佳答案
您可以使用扫描线算法和多重集在 O(N log N)
时间内解决它:
让我们为每个供应商创建两个事件:她开始销售商品的时刻和她结束销售的时刻。我们还将为每次我们感兴趣的时间创建一个“检查”事件。
现在我们将按时间对事件列表进行排序。
对于每个事件,我们执行以下操作:如果它是开始事件,我们将新价格添加到多重集。否则,我们将其删除。
在任何时刻,答案都是多重集中的最小元素,因此我们可以高效地回答每个查询。
如果多重集支持“快速”(即 O(log N)
或更好)插入、删除和查找最小元素,则此解决方案使用 O(N log N)
时间和 O(N)
空间。 Java 标准库中没有多集,但您可以使用 TreeSet
对 (price, vendor_id)
来解决此限制。
关于java - 考虑以下算法的更优解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41394783/