FIND SHELTER

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Greedy algorithm.

DIFFICULTY LEVEL:

Easy.

PROBLEM STATEMENT(SIMPLIFIED):

Nishant is lost along with his N−1 wandering friends. Now they have to find some shelter. Nishant and his N−1 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)−1 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.

See original problem statement here

For Example :

1
5
1 2 3 4 5
9 5 6 10 12

1 is closest to 5,2 is closest to 6, 3 to 9 ,4 to 10 and 5 to 12.
The maximum time is taken by 5th friend to reach x=12 i.e. 7.
You can try any other combination and you will notice that everytime you end up getting more time.

Why?? Look at this picture.

OBSERVATION:

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.

Can you observe what this problem demands?

1. Start traversing from the beginning .

2. Always make the choice that seems to be the best at that moment.

SOLVING APPROACH:

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.

Wait.Does this sound like a greedy problem??

Indeed it is!

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.

1. sort the input array of positions of Nishant and his friends.

2. Also,sort the array of positions of shelter.

3. Take the absolute difference of pi and xi for each i.

4. The maximum of the difference obtained in step 3 is the answer.

SOLUTIONS:

#include <stdio.h>

    void main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
     {
      int n, i, j, tmp;
      scanf("%d", &n);
      int arr1[n].arr2[n];
       for(i=0;i<n;i++)
            {
          scanf("%d",&arr1[i]);
        }
        for(i=0;i<n;i++)
            {
          scanf("%d",&arr2[i]);
        }

    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            if(arr1[j] <arr1[i])
            {
                tmp = arr1[i];
                arr1[i] = arr1[j];
                arr1[j] = tmp;
            }
        }
    }
    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            if(arr2[j] <arr2[i])
            {
                tmp = arr2[i];
                arr2[i] = arr2[j];
                arr2[j] = tmp;
            }
        }
    }
    int mx=0;
    for(i=0; i<n; i++)
    {
        int d=abs(arr1[i]-arr2[i]);
        if(d>mx)
        mx=d;
    }
            printf("%d\n",mx);
    }

#include <bits/stdc++.h>
     using namespace std;
     int solve(vector<int> pos,vector<int> shelter) 
     { 
        if (pos.size() != shelter.size()) 
           return -1; 
        sort(pos.begin(),pos.end());
        sort(shelter.begin(),shelter.end());
        int size = pos.size(); 
        int max = 0; 
        for (int i=0; i<size; i++) 
            if (max < abs(pos[i]-shelter[i])) 
                max = abs(pos[i]-shelter[i]); 

        return abs(max); 
    } 

    int main()
    {  


    int t;
    cin>>t;
     while(t--)
    {
    int n;
     cin>>n;
    vector<int> v,v1;
    int x;
    for(int i=0;i<n;i++)
    {
     cin>>x;
     v.push_back(x);
    }
     for(int i=0;i<n;i++)
    {
     cin>>x;
     v1.push_back(x);
     }
     cout<<solve(v,v1)<<endl;;
    }
    return 0;
    }

import java.util.*;

    class shelter {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int p[]=new int[n];
            int a[]=new int[n];
            for(int i=0;i<n;i++)
            {
                p[i] = sc.nextInt();
            }
            for(int i=0;i<n;i++)
            {
                a[i] = sc.nextInt();
            }
            Arrays.sort(p);
            Arrays.sort(a);
            int max=0;
            for(int i=0;i<n;i++){
                int x = (int)Math.abs(p[i] - a[i]);
                if(x>max){
                    max=x;
                }}
                System.out.println(max);

        }
    }
    }

def solve(pos, shelter):
	
	if len(pos) != len(shelter):
		return -1
	
	pos.sort()
	shelter.sort()
	size = len(pos)
	max_ = 0
	for i in range(size):
		if max_ < abs(pos[i] - shelter[i]):
			max_ = abs(pos[i] - shelter[i])
	return abs(max_)

for _ in range(int(input())):
	
	n = int(input())
	v = list(map(int,input().split()))
	v1 = list(map(int,input().split()))
	print(solve(v, v1))
# your code goes here

[forminator_quiz id="1444"]

This article tried to discuss Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.