关于以下算法的更优化解决方案的思考

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中的时间相对应，如果价格较低，则更新价格然后是与那个时间相对应的旧的，然后在供应商类别中列出存储对应于特定价格的所有时间。

但上面的解决方案是花费O（n2）时间复杂度，所以寻找一些花哨的DS或方法来解决这个在较短的时间复杂度。

Answer 1

您可以使用扫描线算法来解决它在O(N log N)时间多集：

1. 让我们为每个供应商两个事件：她开始出售的物品，她结束时刻的时刻。我们还会为每次感兴趣的时间创建一个“支票”活动。

2. 现在我们将按照时间排序活动列表。

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

4. 在任何时候，答案是multiset中最小的元素，所以我们可以有效地回答每个查询。

如果多重集支持“快”（即，O(log N)或更好）的插入，缺失和寻找最小的元素，这种解决方案使用O(N log N)时间和O(N)空间。 Java标准库中不存在多个集合，但您可以使用对(price, vendor_id)来解决此限制。