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).
In 2nd case, when no tables are available, what if we ask that particular customer to leave, who will be giving the order least number of times after that? Why choose someone who will give the order farthest in time? Can you prove why it is correct?
In 2nd case, when no tables are available, what if we ask that particular customer to leave, who will be giving the order least number of times after that? Why choose someone who will give the order farthest in time? Can you prove why it is correct?
@ ketanhwr Thumbs up! Iâve done the same way.
@ Editorialist I donât know if I can ask this here. Can you give me a test case which differentiates your approach with the one mentioned by ketanhwr ?
Even I implemented the same Optmal age Replacemennt Algo, and for commented test cases too its working correctly. Can somebody tell me where I am wrong.
Can someone pls provide me the corner case for which my code is giving wrong ans
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int numberOfTestCase = Integer.parseInt(st.nextToken());
for (int i = 0; i < numberOfTestCase; i++) {
st = new StringTokenizer(br.readLine());
int noOfTables = Integer.parseInt(st.nextToken());
int noOfOrders = Integer.parseInt(st.nextToken());
List<Integer> orders = new ArrayList<Integer>();
st = new StringTokenizer(br.readLine());
int count = 0;
List<Integer> list = new ArrayList<Integer>();
while (st.hasMoreElements()) {
int orderNumber = Integer.parseInt(st.nextToken());
list.add(orderNumber);
}
for (int j = 0; j < noOfOrders; j++) {
if (orders.size() == noOfTables) {
if (!orders.contains(list.get(j))) {
int temp = 0;
int found = -1;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int o : orders) {
boolean present = false;
int count1 = 0;
for (int r = j+1 ; r < list.size(); r++) {
if (list.get(r) == o) {
present = true;
count1++;
map.put(count1, o);
}
}
if (!present) {
found = 0;
break;
}
temp++;
}
if (found != 0) {
Map<Integer, Integer> m = sortByKeys(map);
Object myKey = m.keySet().toArray()[0];
temp = orders.indexOf(m.get(myKey));
}
orders.set(temp, list.get(j));
count++;
}
} else {
if (!orders.contains(list.get(j))) {
orders.add(list.get(j));
count++;
}
}
}
log.write("" + count);
log.newLine();
log.flush();
}
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public static <K extends Comparable, V extends Comparable> Map<K, V> sortByKeys(
Map<K, V> map) {
List<K> keys = new LinkedList<K>(map.keySet());
Collections.sort(keys);
// LinkedHashMap will keep the keys in the order they are inserted
// which is currently sorted on natural ordering
Map<K, V> sortedMap = new LinkedHashMap<K, V>();
for (K key : keys) {
sortedMap.put(key, map.get(key));
}
return sortedMap;
}
For all âWhats wrong with my approachâ questions, here is a python script to generate input file
from sys import stdout
from random import randint
T = randint(1,100)
stdout.write(str(T)+"\n")
while T:
N = randint(1,200)
M = randint(1,400)
stdout.write(str(N)+" "+str(M)+"\n")
while M:
stdout.write(str(randint(1,400))+" ")
M = M-1
stdout.write("\n")
T = T-1
Take any successfull solution compile it. Compile your solution and compare output of both. And seriously, stop expecting people to debug your code for you. Very few people have the time and commitment for that. Learn to debug yourself.
You can tweak the parameters to generate smaller testcases that you can debug with pen and paper.
Ok, I deduced the âfarthest of timeâ thing after I was doing something with frequency, but still I kept getting WA even when I used Deque for same implementation. Can I please get the test file or case for which my code fails, I am pretty sure it is correct. WA, CLETAB
