CareerCup

This question is poorly defined with several vague terms and without stating the objective clearly. I am assuming that selecting the *most efficient* elevator means the user should be able to reach his destination in the least amount of time and the lift movement should also be minimum.

Though the problem has been posed as an optimization problem, there are some serious caveats for it to be one. The problem in reality is inherently probabilistic in nature for the state of the system is ever changing and unpredictable.

An attempt can however be made to find out an optimal choice at a given snapshot of the system when a user wants to navigate. This includes several assumptions like the wait time at each lift is constant and is uniform across all the lifts and independent across the lifts.

If we assume there are k lifts and floor numbers start from 0 and go up to 'max_floor' we can have 3 arrays to manage the state of the system.

updown[1..k]: holding 0/1 to denote whether the lifts are moving up(=0) or down(=1)
currfloor[1..k] current floor the lift is on
nextfloor[1..k] floor the lift is headed to. If nextfloor[] were a two dimensional array with all future stops registered, the problem would get tougher..

If the user currently on 'presentFloor', and wishes to go to 'destFloor', based on the user's choice to go up or down, we select a subset of the lifts from updown[] array.

For the selected subset of lifts, compute the values vi = mi/ni, where mi = f(presentFloor, destFloor, nextFloor[i], i) and ni=g(presentFloor, currentFloor[i], i)

f(presentFloor, destFloor, nextFloor, i)  {
nextFloor = abs(nextFloor - updown[i] * max_floor)
destFloor= abs(destFloor- updown[i] * max_floor)
presentFloor= abs(presentFloor- updown[i] * max_floor)

if (nextFloor-presentFloor) /(destFloor- presentFloor) > 1)
  return 1
else
  return (destFloor- presentFloor) /(nextFloor-presentFloor)
}

g(presentFloor, currentFloor) {
  return presentFloor - currentFloor
}

Rationale behind computing vi's: vi's is the ratio of max_possible_travel_time_to_dest_floor to min_waiting_time_for_a_lift_to_arrive, max_possible_travel_time_to_dest_floor here is roughly obtained my minimizing the stop time en route the destFloor. However, if nextfloor[] were a 2D array with all future stops registered, the value of max_possible_travel_time_to_dest_floor has to be obtained by minimizing the stop time en route the destFloor, which is nothing but c*no_of_stops_between_current_floor_and_next_floor_or_dest_floor, for some constant c.

So, To choose a particular lift sort vi's and pick the one with max vi

The above greedy heuristic should work and it's correctness can be established by exchange argument, though I don't own the rigor at the moment to prove it.

LiftName(Current floor, Destination floor)
Destination floor = -1 if lift is still
A(4,0)
B(2,4)
C(0,-1)
D(1,0)
E(2,-1)

Passenger P(1,4)

DistA = Dist(4,0,1,4)
DistB = Dist(4,0,1,4)
DistC = Dist(4,0,1,4)
DistD = Dist(4,0,1,4)
DistE = Dist(4,0,1,4)

int TotalDist(int a, int b, int c, int d)
{
    int nTotalDist = 0;

    if(a>c>b || a<c<b)   //Check if pickup is on the way
         return Dist(a,c);
    else      
          nTotalDist += Dist(a-b);

         nTotalDist +- Dist(c-b);
         nTotalDist += Dist(c-d);
}

int Dist(int a, int b)
{
   if(b == -1)
      return 0;
  else if(a>c>b)
      return b-a-c;
     return b-a;
}