A certain one-way street has m parking spaces in a row, numbered 1 through m. A

Question

A certain one-way street has m parking spaces in a row, numbered 1 through m. A man and his dozing wife drive by, and suddenly she wakes up and orders her husband to park immediately. He parks at the first available space unless there are no parking spaces left that he can get to without backing up (i.e., if his wife awoke when the car approached space k, but spaces k, k+1, …, m are already occupied) in which cases he apologizes to her and drives on. Suppose the above scenario occurs for n different cars, where the j th wife wakes up just in time to park in space aj. For example when m = n = 9 and the j th wife wakes at < a1, a2, … a9> = <3,1,4,1,5,9,2,6,5>, the cars are parked as follows: Car 2 4 1 3 5 7 8 9 6 space 1 2 3 4 5 6 7 8 9 Design an efficient algorithm determining in which space, if any, a car parks.

Explanation / Answer

import java.util.*;

public class Parking{

public static void main(String []args){
Scanner ob = new Scanner(System.in);
int m, i, n, j;
System.out.println("Enter no of parking space:");
m = ob.nextInt();
int[] parkSeq = new int[m];
  
//initialise parkSeq with 0
for(i = 0; i < m; i++)
parkSeq[i] = 0;
  
System.out.println("No of cars:");
n = ob.nextInt();
int[] wakeSeq = new int[n];
  
//to take input for wake sequence
System.out.println("Enter wake seq:");
for(i = 0; i < n; i++)
wakeSeq[i] = ob.nextInt();
  
// to find park seq
for(i = 0; i < n; i++){
j = wakeSeq[i] - 1; // as index starts from zero
while(j < m){
if(parkSeq[j] == 0){
parkSeq[j] = i + 1;
break;
}
j++;
}
}
  
//to display park sequence
for(i = 0; i < m; i++){
if(parkSeq[i] == 0)
System.out.print(" _");
else
System.out.print(" " + parkSeq[i]);
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.