CODEWITHSUNDEEP
javaalgorithmdata-structures
Girish
Girish

Reputation: 1717

Thinking about more optimal solution for below algorithm

There are n vendors on amazon who are selling the product at particular price at particular time, I have to design an algorithm which will select the product with least price at particular time.

For ex: For below set of input

Input Format :

<StartTime, EndTime, Price of product by this vendor in this time frame>
1 5 20 
3 8 15
7 10 8

Output should be: 

1 2 20
3 6 15
7 10 8

I have done with the solution by storing the prices corresponding to time in hashmap, and updating the price if there exist a price lesser then the old one corresponding to that time, and then made the list in vendor class to store all the times corresponding to the particular price.

But above solution is taking O(n2) time complexity, so searching for some fancy DS or approach to solve this in lesser time complexity.

Upvotes: 2

Views: 118

Answers (1)

kraskevich
kraskevich

Reputation: 18556

You can use a sweep line algorithm and a multiset to solve it in O(N log N) time:

  1. Let's create two events for each vendor: the moment she starts selling the item and the moment she ends. We'll also create one "check" event for each time we're interested in.

  2. Now we'll sort the list of events by their times.

  3. For each event, we do the following: if it's a start event, we add the new price to the multiset. Otherwise, we remove it.

  4. At any moment of time, the answer is the smallest element in the multiset, so we can answer each query efficiently.

If the multiset supports "fast" (that is, O(log N) or better) insertions, deletions and finding the smallest element, this solution uses O(N log N) time and O(N) space. There is no mulitset in the Java standard library, but you can use a TreeSet of pairs (price, vendor_id) to work around this limitation.

Upvotes: 1

Related Questions