Skip to main content

Car Parking Problem

There is n parking slots and n-1 car already parked.
Lets say car parked with initial arrangement and we want to make the car to be parked
to some other arrangement.

Lets say n = 5, inital = free, 3, 4, 1, 2
desired = 1, free, 2, 4 ,3

Give an algorithm with minimum steps needed to get desired arrangement.
Told by one of my friend and after a lot of search i really got a nice solution.
I will post solution in comment part
Labels:

Comments

  1. AshuDecember 13, 2009 at 10:17 PM

    Let D={d_1,d_2,..,d_n} be the desired parking arrangement
    and C={c_1,c_2,...c_n} be the current parking arrangement.
    Let M=\sum_{i=1]^{n} (c_i!=d_i)

    1)Let e be the index of the empty slot in the current arrangement(C).
    2)Define a boolean variable X .
    X=1 if the empty slot is matched and 0 otherwise
    ie
    X=1 if ∃ i : c_i=d_i=Empty
    X=0 if ∃! i : c_i=d_i=Empty
    3)If X=0, let k be the index such that c_k=d_e, set M=M-1 if d_k!=free, set M=M-2 if d_k=free
    4)If X=1, let k be the smallest index such that c_k!=d_k and set M=M+1
    5)Put the car currently parked in c_k to c_e
    6)Define C' such that C'[m]=C[m] if m!=k and m!=e.Set C'[k]=C[e] and C'[e]=C[k]
    7)Set C=C'
    8)If M>0 goto step 1, otherwise exit

    Got it from algorithm community ..courtesy Balakrishnan.

    ReplyDelete
  2. AnonymousJuly 9, 2010 at 11:20 PM

    the question is not clear??

    ReplyDelete
  3. AnonymousJuly 9, 2010 at 11:34 PM

    wat does M=\sum_{i=1]^{n} (c_i!=d_i) mean.

    ReplyDelete

Post a Comment

Popular posts from this blog

JDBC connection factory

  Class ConnectionManager {   Queue<Connection> availableConnection;   List <Connection> allotedConnection; ConnectionManager( Integer noOfConnections, ConnectionPoperties props ) {     //Create the no of connection objects and assign to avaialbleConnection } Conection getConnection() {     syncronized( this.class) { if (availableConnection.isEmpty() ) {          throw ConnectionExhausted();       }       conn = availableCOnnection.poll();       alottledConectiion.add(conn); } return conn; } synchronized Conection releaseConnection(Connection conn) {        alottedconnection.remove(conn);    avaialbleConection.add(conn); }
Post a Comment
Read more

Median of Five Numbers

U have 5 NOs , X1,X2,X3,X4,X5 With minimum no. of comparisons we have to find a median. SWAP(X,Y) function is available to u . I have a answer of six comparisons and eight swaps....wait for people to find out by themselves.
1 comment
Read more