The Smart Movers (Algorithm 1)

Points : 30

Sam is algorithms consultant of XYZMovers, which provides packing and moving of goods in New York city.

XYZMovers works as follows.It has its agents at a variety of fixed locations of the city. Every "Pack and Move" is headed by an agent with help of some workers. Each time a user needs a service, he needs to register his request at the XYZMover's website with details of the pickup time and location and also drop off time and location.

XYZMovers need to make sure that there is enough number of agents at each location at the start of the day so that at least, one agent is always available for every pickup. However, as it is expensive to hire more agents, so minimizing the total number of agents is an important goal. So what is required is an algorithm to process user requests so as to minimize the total number of agents that must be placed initially at various locations.

In a nutshell,the problem is to process a list of user requests which are tuples of form (l1,t1,l2,t2) where l1 is pickup location and l2 is drop off location t1 and t2 being pickup and drop off times respectively.

Obviously, when a client makes a pickup from location A, the number of agents at A is decreased by 1 and on a drop off to location B, the number of agents at B increases by 1. Assume that there are m locations l1 to lm.

Help Sam in designing an efficient algorithm to accomplish this task. You also need to explain time and space complexities of your algorithm.

Points Distribution

• 25 points for the algorithm
• 5 points for providing space and time complexities and its explanation

Solution

We note the following property (call it Property 1):
if a location starts with c+1 agents, then at all times it has exactly one more agent than if it had started with only c agents. This motivates the following algorithm:

1.) Take two arrays:
    arr_initial[num_locations] // contains initial number of agents at each location
    arr_current[num_locations] // contains current number of agents at each location
for each location, set its initial number of agents to zero.
    arr_initial[num_locations] = {0} // Initialize to zero
    arr_current[num_locations] = {0} // as initially, there are no agents at any location.
 
2.) Now sort the pick-ups and drop-offs by time; in case of ties, put drop-offs first.

Each request (l1,l2,t1,t2) consists of two events:
A pickup: from location l1 at time t1 say (l1,t1,p)
A drop-off: at location l2 at time t2 say (l2,t2,d)

Sort these by time.

Simulate the day by iterating over the sorted list of events.
    At a drop-off event,
    increase the number of agents currently at the specified location by one.
    i.e at drop-off at location loc, arr_current[loc] += 1;

    similarly, at a pick-up event at location loc, do the following:
    if ( arr_current[loc] > 0 )
     arr_current[loc]-- ; //simply decrease that number by one;
    otherwise arr_current[loc] == 0,
    So increase both the initial number of agents and
    the number of agents currently at that location by one,
    i.e arr_initial[loc]++;
        arr_current[loc]++;
    then decrease the number of agents currently at the location by one as usual.
        arr_current[loc]--;
     
3.) When all the events have been iterated over,
return the array containing the initial numbers of agents at each
location.

Proof of correctness

The algorithm is correct because of the greedy-choice property: whenever we decide to increment the initial number of agents for a particular location loc from c to c+1,(property 1) suggests that no feasible solution puts fewer than c+1 agents at location loc. So incrementing is safe. Also, as we passed the entire day with no deficit of agents at any location, the solution is feasible.

Complexity

• Time: O(nlogn) //for sorting the events.
• Space:O(n) // linear in number of locations and events

Post your queries regarding the solution at Algorithm 1 Forum Thread.