{"id":1442,"date":"2020-06-11T04:07:53","date_gmt":"2020-06-11T04:07:53","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1442"},"modified":"2022-03-28T23:20:48","modified_gmt":"2022-03-28T23:20:48","slug":"find-shelter","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-shelter\/","title":{"rendered":"FIND SHELTER"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm.<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Easy.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Nishant is lost along with his N\u22121 wandering friends. Now they have to find some shelter. Nishant and his N\u22121 friends have some position along x axis(pi) and there are N shelters along the x axis at some position(xi).Each shelter can accommodate only one person and travelling from pi to (pi)\u22121 or (pi)+1 takes one minute. Now Nishant and his friends start looking for shelter. Nishant wants to know the minimum time after which all of hi friends will find shelter. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
1\n5\n1 2 3 4 5\n9 5 6 10 12\n\n1 is closest to 5,2 is closest to 6, 3 to 9 ,4 to 10 and 5 to 12.\nThe maximum time is taken by 5th friend to reach x=12 i.e. 7.\nYou can try any other combination and you will notice that everytime you end up getting more time.\n\nWhy?? Look at this picture.\n<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
In the above test case, p1 anf f4 (postion1 and friend4) may deceive you with 0 time ,but notice that on any other combination for rest of the friends, minimum time increases.<\/p>\n
Can you observe what this problem demands?<\/p>\n
    \n
  1. \n
    Start traversing from the beginning .<\/p>\n<\/li>\n
  2. \n
    Always make the choice that seems to be the best at that moment.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
    Always make the choice that seems to be the best at that moment. This means that make a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.<\/p>\n
    Wait.Does this sound like a greedy problem??<\/em> <\/p>\n
    Indeed it is!<\/p>\n
    Since a Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized,we traverse the list of given positions from the starting point and keep choosing the most suitable destination for that point without going back and reversing the direction.<\/p>\n
      \n
    1. \n
      sort the input array of positions of Nishant and his friends.<\/p>\n<\/li>\n
    2. \n
      Also,sort the array of positions of shelter.<\/p>\n<\/li>\n
    3. \n
      Take the absolute difference of pi and xi for each i.<\/p>\n<\/li>\n
    4. \n
      The maximum of the difference obtained in step 3 is the answer.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      SOLUTIONS:<\/h3>\n\t\t\t\t\t\t