27/180: GeeksForGeeks : Find the point where maximum intervals overlap.

In this problems we need to find out that particular time when there were the maximum guests. Let’s say we have maintained a log for arrival and departure and from there we need to figure out the number of guest present at particular interval.

For example — Input -> arrival[] = {1, 2, 10, 5, 5}

departure[] = {4, 5, 12, 9, 12}

By this input we mean that if some guest arrived at 1 would exit at 4 and so on.

So what we can do to solve this problem is, we can sort both the arrays and we can process both arrays in merged way and can maintain a list of number of guests at every arrival or exit.

Let’s say after sorting my array for arival becomes {1, 2, 5, 5, 10}

array for departure becomes {4, 5, 9, 12, 12}

Event Type         Interval        Number of Guests
Arrival              1                 1
Arrival              2                 2
Exit                 4                 1
Arrival              5                 2
Arrival              5                 3
Exit                 5                 2
Exit                 9                 1
Arrival              10                2
Exit                 12                1
Exit                 12                0

And now we can find out that the maximum guests were present at the interval 5, which is 3

Let’s code this out

public static void getMaximumGuest(int[] arrival, int[] exit, int n){
     Arrays.sort(arrival);
 Arrays.sort(arrival);
        int i = 1, j = 0;
        int curr_guests = 1; int max_guest = 1;
        int time_interval = arrival[i];
        while(i < n && j < n){
      if(arrival[i] <= exit[j]){
  curr_guests++;
                if(max_guest < curr_guests)
  { 
                     max_guest = curr_guests;
   time_interval = arrival[i];
                }
                i++;
             }else{
  curr_guests--;
                j++;
      }
  
        }
 System.out.println("Maximum no. of guests = "+ max_guest + " at time " + time_interval);
    }