Interview Question
Country: United States
1. The question is not clear.
maximum no of customers can get the rooms
By the example, it seems that is "maximum no of customers can get the favorite rooms".
2. If it is just the favorite rooms, it becomes to just arrange by every room and sum all rooms. All below discussion based on this assumption.
3. For every room, "uuuouou" 's answer seems reasonable.
Your problem is a mixture of "Bin Packing" (assign different objects with volumes to different bins with finite capacity) and "Agent Matching" (assignment based on preference) and hence,
NP-complete. So in general, any solution might be as good as others, i.e., worst time exponential.
What I suggest, is a backtracking algorithm (aka Branch and Bound). This is just to have a first crack at the problem. The idea behind branch and bound is very simple:
A- Browse all (worst case) possibilities (through recursion, for instance)
B- Before each assignment check if we bound
Bounding: Cleverly deducing whether or not we need to delve in deeper. For example, you have already found a solution to serve 3 customers. Now you are checking customer 3/4 and you have assigned only one yet. Obviously, the best you can do is to assign only one more customer which brings you to "2" and this is a worst solution than what you already have. So just don't bother!
The code is in Java.
Main Algorithm:
// Assign customer with ID = c_id
public void RunAssignment(int c_id) {
// Here goes nothing... (worst time exponential)
// Trying to assign customer id = c_id
/// HERE IS THE BOUNDING PART (a very simplistic one indeed)
int customers_left = customers.length - c_id; // How many more customers left to assign
if (curr_customers_in + customers_left < max_customers_assigned) // There is no way to find a better assignment since we already have a better solution
return;
// Check all rooms that this customer likes
for (int room_index : customers[c_id].preferred_rooms) {
// Can we check this customer in? (Here you resolve the clashes)
if (rooms[room_index].CheckIn(customers[c_id])) {
// YES!
// Count one more
curr_customers_in++;
// Is it a better or equally good as our best one so far?
if (curr_customers_in >= max_customers_assigned) {
// YES!
max_customers_assigned = curr_customers_in;
// Print it!
AnnounceSolution();
}
// Do we have anybody left?
if (c_id < customers.length - 1) {
// Assign next!
RunAssignment(c_id + 1);
// To brows other options, check this customer out.
rooms[room_index].CheckOut(customers[c_id]);
// Count one out
curr_customers_in--;
// Try to assign next (this time, our current customer is not assigned anymore!)
RunAssignment(c_id + 1);
}
else {
// No? Just check out to try next room (not necessary at this point, but just to make sure we have all possible solutions)
curr_customers_in--;
rooms[room_index].CheckOut(customers[c_id]);
}
}
}
}
I am using two types of Objects: Customer and Room
First Room:
public class Room {
public static int MaxHour = 300;
public ArrayList<Customer> customers;
int ID;
boolean[] hours;
// Sets the room ID
public Room(int ID) {
customers = new ArrayList<Customer>();
hours = new boolean[Room.MaxHour];
this.ID = ID;
}
/**
*
* @param c Customer (object)
* @return True if "c" can be checked in. If so, the corresponding hours of occupancy are marked off. Otherwise, just say false.
*/
public boolean CheckIn(Customer c) {
for (int i = c.hour_in; i < c.hour_out; i++)
if (hours[i])
return false;
for (int i = c.hour_in; i < c.hour_out; i ++)
hours[i] = true;
customers.add(c);
return true;
}
/**
* Release the hours assigned to a customer.
* @param c Check out this customer.
*/
public void CheckOut(Customer c) {
for (int i = c.hour_in; i < c.hour_out; i++)
hours[i] = false;
customers.remove(c);
}
// For printing solution
@Override
public String toString() {
String msg= "Room " + Integer.toString(ID) + " serves ";
if (customers.isEmpty())
msg = msg + " no one!";
else
for (Customer c : customers)
msg = msg + "[" + c.toString() + "]";
return msg;
}
}
And now the Customer class (nothing to it)
public class Customer {
// Set the corresponding info.
public Customer(int ID, int hours_in, int hours_out, int[] rooms) {
this.ID = ID;
this.hour_in = hours_in - 1;
this.hour_out = hours_out - 1;
this.preferred_rooms = rooms;
}
int ID, hour_in, hour_out;
public int[] preferred_rooms;
@Override
public String toString() {
return "Customer " + Integer.toString(ID);
}
}
Group customers according to their favorite room's number:
1) Map<Integer, List<Customer>>
2) Sort each customer's list according to arrival time (you can also use Queue instead of list and write custom comparator. it might be more realistic :) )
3) for each room iterate over its queue
- first customer get access
- counter++;
- set variable departureTime = customer.endingTime
if(nextCustomer.startTime > departureTime){
departureTime = nextCustomer.endingTime
counter++
}
Yes, it provides max count. Each time a new customer is assigned to the room increment counter. Just like in the example. At the end you will have max.
It's just like the activity arrangement problem. Greedy algorithm will work.
- uuuouou January 03, 2014(1)divide customers into several groups in which members have the same favourite room. customers in different groups are unrelated with each other.
(2)sort each group according to ending time.
(3)for each group, always add the next customer whose ending time is the earliest and whose starting time is not earlier than last one's ending time into the room's schedule.