PROBLEM LINK:
Author: Vinayak Garg
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu
DIFFICULTY:
Simple
PREREQUISITES:
Greedy Algorithms, Simulation
PROBLEM:
You have N(<201) tables for costumers. M(<401) constumers will place orders. Each customer will place an order and if he is not already seated, a table will be cleaned and will be given to him. If no tables are empty some customer(of your choice) will be asked to leave and the new costumer will be placed on the empty table after cleaning. You are given the sequence in which customers place their orders. Find the minimum number of tables that must be cleaned.
EXPLANATION:
Let’s say a customer comes with an order:
If he is already seated, do nothing. We don’t have to clean a table.
If not seated, two cases arrive:
- Empty table is available: We clean the table and give a table to him. Any empty table will work.
- No empty table is available: We have to remove someone from the table. We would prefer to remove someone who doesn’t places an order in future. If such customers are seated, we can remove anyone from them. If we remove someone who will order in future, we’ll have to clean one extra table which we won’t have to if we pick greedily. If no such customer is present who’ll NOT order in future, we’ll pick a customer who will order in future in farthest of time. This will ensure that minimum number of swaps are to be made.
Once the greedy approach is clear, implementation is very easy. It can be solved in O(N*M). Using heaps/priority queue we can also solve in O(N log M).
Links: The theoretically optimal page replacement algorithm.