java - 考虑以下算法的更优解决方案

Question

亚马逊上有 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 或方法来以较小的时间复杂度解决这个问题。

Answer 1

您可以使用扫描线算法和多重集在 O(N log N) 时间内解决它:

1. 让我们为每个供应商创建两个事件:她开始销售商品的时刻和她结束销售的时刻。我们还将为每次我们感兴趣的时间创建一个“检查”事件。

2. 现在我们将按时间对事件列表进行排序。

3. 对于每个事件，我们执行以下操作:如果它是开始事件，我们将新价格添加到多重集。否则，我们将其删除。

4. 在任何时刻，答案都是多重集中的最小元素，因此我们可以高效地回答每个查询。

如果多重集支持“快速”(即 O(log N) 或更好)插入、删除和查找最小元素，则此解决方案使用 O(N log N) 时间和 O(N) 空间。 Java 标准库中没有多集，但您可以使用 TreeSet 对 (price, vendor_id) 来解决此限制。