Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
package com.omt.learn.geekforgeek.greedy; import org.apache.commons.lang3.SystemUtils; import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class NumberOfStationRequired { private static class Schedule { float arrivalTime = -1; float departureTime = -1; public Schedule(float at, float dt) { this.arrivalTime = at; this.departureTime = dt; } } public static void main(String args[]) { List<Schedule> allTrains = new ArrayList<>(); allTrains.add(new Schedule(9.00f,9.10f)); allTrains.add(new Schedule(15.00f,19.00f)); allTrains.add(new Schedule(9.40f,12.00f)); allTrains.add(new Schedule(11.00f,11.30f)); allTrains.add(new Schedule(18.00f,20.10f)); allTrains.add(new Schedule(9.50f,11.20f)); System.out.println("Total Station Required :"+findMinStationRequired(allTrains)); } private static int findMinStationRequired(List<Schedule> allTrains) { int totalStations = 1; Map<Float,Integer> timeArrivalDepartureMap = new TreeMap<>(); for(Schedule schedule : allTrains) { if(!timeArrivalDepartureMap.containsKey(schedule.arrivalTime)){ timeArrivalDepartureMap.put(schedule.arrivalTime,0); } if(!timeArrivalDepartureMap.containsKey(schedule.departureTime)) { timeArrivalDepartureMap.put(schedule.departureTime,0); } timeArrivalDepartureMap.put(schedule.arrivalTime,timeArrivalDepartureMap.get(schedule.arrivalTime)+1); timeArrivalDepartureMap.put(schedule.departureTime,timeArrivalDepartureMap.get(schedule.departureTime)-1); } int tempCount = 0; for (Float key : timeArrivalDepartureMap.keySet()) { tempCount+=timeArrivalDepartureMap.get(key); if(tempCount > totalStations) { totalStations = tempCount; } } return totalStations; } } |
Output:
|
1 |
Total Station Required :3 |