Assume you're trying to model a parking lot with multiple types of slots available. The slots could have different prices based on certain criterion like distance from the entrance, the maximum size of the vehicle it can fit, etc.
The smaller vehicles can be fit into the larger spots if the customer is willing to pay for it. The slot price of same size could also be different.
I'm imagining a priority queue could be helpful in getting the next best spot available to park a new vehicle. We get the best spot available and ask the customer to park their vehicle in that spot if they agree.
Let's say a customer comes with a vehicle and we give them the best spot available but that is not within their budget and asks for a different spot. Fine, we take out the next best spot available with lower price. At this point, all the spots which are of higher price can't be put back into the priority queue. They need to be stored in a different data structure, maybe a stack or another priority queue itself.
For some reason, none of the slot prices is favourable to the customer and they are notified of the exception and now we have all the spots in the auxiliary data structure. If the auxiliary data structure is a priority queue, we can replace it with the primary priority queue without any additional runtime consumption. Or maybe, compare the sizes the two queues and put the items in the smaller queue into the bigger one and make that the primary queue.
Alternatively, we can use a stack as the auxiliary data structure and we'll need to put everything back into the primary queue as and when needed.
I'm troubled in deciding which of the alternatives would have the better runtime complexity in the long run. Would be glad if anyone could help out.
Aucun commentaire:
Enregistrer un commentaire