Minimum Platform Required Program

Minimum platform required  program

(Dynamic Programming :)

-------------------------------------------------------

The Minimum platform required  program of dynamic programming.This question has been collected from geeksforgeeks.com.

link : https://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/

Here I tried to give a simple solution of this program by using map.The logic will be same as per explained in the screen shot below or in the site geeksforgeeks.com.

I  have only tried to give a simple code solution to the program.

Minimum Number of Platforms Required for a Railway/Bus Station

Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits.
We are given two arrays which represent arrival and departure times of trains that stop.

Examples:

Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
Explantion: There are at-most three trains at a time (time between 11:00 to 11:20)

Input: arr[] = {9:00, 9:40}
dep[] = {9:10, 12:00}
Output: 1
Explantion: Only one platform is needed.

Simple Solution:

• Approach: The idea is to take every interval one by one and find the number of intervals that overlap with it. Keep track of the maximum number of intervals that overlap with an interval. Finally, return the maximum value.
• Algorithm:
  1. Run two nested loops the outer loop from start to end and inner loop from i+1 to end.
  2. For every iteration of outer loop find the count of intervals that intersect with the current interval.
  3. Update the answer with maximum count of overlap in each iteration of outer loop.
  4. Print the answer.

• Complexity Analysis:
  • Time Complexity: O(n^2).
    Two nested loops traverse the array, so the time complexity is O(n^2).
  • Space Complexity: O(1).
    As no extra space is required.

Efficient Solution:

• Approach: The idea is to consider all events in sorted order. Once the events are in sorted order, trace the number of trains at any time keeping track of trains that have arrived, but not departed.
  For example consider the above example.

  arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}
  dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
  
  All events are sorted by time.
  Total platforms at any time can be obtained by
  subtracting total departures from total arrivals
  by that time.
  
   Time      Event Type     Total Platforms Needed 
                                 at this Time                               
   9:00       Arrival                  1           1
   9:10       Departure                0           1-1=0
   9:40       Arrival                  1           0+1=1
   9:50       Arrival                  2           1+1=2
   11:00      Arrival                  3           2+1=3
   11:20      Departure                2           3-1=2
   11:30      Departure                1           2-1=1
   12:00      Departure                0           1-1=0
   15:00      Arrival                  1           0+1
   18:00      Arrival                  2 
   19:00      Departure                1
   20:00      Departure                0
  
  Minimum Platforms needed on railway station 
  = Maximum platforms needed at any time 
  = 3  
  

  Note: This approach assumes that trains are arriving and departing on the same date.

In the above logic explained we can observe that , In each arrival we are adding 1 and for each departure we are subtracting 1 after sorting .

=========

CodE

=========

import java.util.*;

public class Main

{

public static void main(String[] args) {

Map<Double,String> m1=new TreeMap<Double,String>();

double arrival[]=new double[]{9.00,9.40,9.50,11.00,11.30,15.00,18.00};

double departure[]=new double[]{9.10,12.00,11.20,11.30,19.00,20.00};

//Adding the arrival time to a map named arrival

for(int i=0;i<arrival.length-1;i++)

{

    m1.put(arrival[i],"arrival");

}

                //Adding the departure time to a map named departure

for(int i=0;i<arrival.length-1;i++)

{

    m1.put(departure[i],"departure");

}

for(Map.Entry<Double,String> entry:m1.entrySet())

{

    System.out.println("key= "+ entry.getKey() +"Value= "+entry.getValue());

}

//Taking a variable count to 0 and an arrayList

    int count=0;

    List<Integer> al=new ArrayList<Integer>();

//take each entry from the map

// if the value is "Arrival"then add 1 to the count

//if the value is "departure" subtract 1 from count

for(Map.Entry<Double,String> entry:m1.entrySet())

{

    if(entry.getValue()=="arrival")

    {

    count ++;

    al.add(count);

    }

    else

    {

       count --;

       al.add(count);

    }

}

for(Integer i:al)

{

    System.out.println(i);

}

//Now acording to the login

//Maximum in the list will be the min number of platform required.

//so sort the array list

//print the last element

Collections.sort(al);

int n=al.get(al.size()-1);

System.out.println("The maximum platform required is :- ");

System.out.println(n);

}

}