Minimum Number of Platforms Required for a Railway Station

You are given arrival and departure times of trains, you have to find out, minimum platforms required.

Once you got new train arrival details,

for(TrainTime time : allTrainTImes){

         If time.arrival is > any train departure{

                  remove one train detail, where departure > new train arrival.

         }

         add this train details to map.

}

Final result is the size of map.

package arrays;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

public class PlatformsRequired {
 private Map<Double, Double> map;

 /**
  * Class represent train time
  */
 public static class TrainTime {
  private double arrival;
  private double departure;

  TrainTime(double arrival, double departure) {
   if (arrival < 0 || departure < 0 || arrival >= 24
     || departure >= 24) {
    throw new IllegalArgumentException(
      "arrival and departutre times are inbetween 0 and 24. arrival : "
        + arrival + " departure : " + departure);
   }
   this.arrival = arrival;
   this.departure = departure;
  }

  public double getArrival() {
   return arrival;
  }

  public double getDeparture() {
   return departure;
  }

 }

 public int getNumberOfPlatForms(List<TrainTime> trainTimes) {
  Objects.nonNull(trainTimes);
  map = new HashMap<>();

  /* Sort trains based on arrival time */
  Collections.sort(trainTimes, new Comparator<TrainTime>() {

   @Override
   public int compare(TrainTime train1, TrainTime train2) {
    double time = train1.getArrival() - train2.getArrival();
    if (time > 0)
     return 1;
    else if (time < 0)
     return -1;
    return 0;

   }

  });

  for (TrainTime tTime : trainTimes) {
   Set<Double> arrivalTimes = map.keySet();
   for (Double arrival : arrivalTimes) {
    /*
     * If new train arrival time is > any one existing train
     * departure time
     */
    if (tTime.getArrival() > map.get(arrival)) {
     map.remove(arrival);
     break;
    }
   }
   map.put(tTime.getArrival(), tTime.getDeparture());
  }
  return map.size();
 }

}

Following is the junit test case for above program.

package arrays;

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.List;

import org.junit.Test;

import arrays.PlatformsRequired.TrainTime;

public class PlatformsRequiredTest {

 @Test
 public void test1() {
  List<TrainTime> trainTimes1 = Arrays.asList(new TrainTime(9.00, 9.10),
    new TrainTime(9.40, 12.00), new TrainTime(9.50, 11.20),
    new TrainTime(11.00, 11.30), new TrainTime(15.00, 19.00),
    new TrainTime(18.00, 20.00));

  List<TrainTime> trainTimes2 = Arrays.asList(new TrainTime(9.00, 9.10),
    new TrainTime(10.00, 11.00), new TrainTime(9.20, 10.20),
    new TrainTime(10.15, 10.45), new TrainTime(10.30, 12.00));

  List<TrainTime> trainTimes3 = Arrays.asList(new TrainTime(9.00, 9.10),
    new TrainTime(9.01, 9.11), new TrainTime(9.02, 9.12),
    new TrainTime(9.03, 9.13), new TrainTime(9.04, 0.14));

  List<TrainTime> trainTimes4 = Arrays.asList(new TrainTime(9.00, 9.10),
    new TrainTime(9.01, 9.11), new TrainTime(9.02, 9.12),
    new TrainTime(9.03, 9.13), new TrainTime(9.04, 9.14),
    new TrainTime(9.14, 9.15));

  List<TrainTime> trainTimes5 = Arrays.asList();
  List<TrainTime> trainTimes6 = Arrays.asList(new TrainTime(9.00, 9.10));
  List<TrainTime> trainTimes7 = Arrays.asList(new TrainTime(9.00, 9.10),
    new TrainTime(8.55, 8.58));

  PlatformsRequired platformsRequired = new PlatformsRequired();

  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes1), 3);
  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes2), 3);
  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes3), 5);
  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes4), 5);
  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes5), 0);
  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes6), 1);
  assertEquals(platformsRequired.getNumberOfPlatForms(trainTimes7), 1);
 }
}

Method 2: Anther approach is, simply sort both arrival and departure times. Whenever you got arrival time, increment the counter, else decrement. Keep track of maximum counter value. Maximum counter value is the number of platforms required.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

public class PlatformsRequired {

 private class TrainTimingType {
  /* 'A' represents Arrival time, 'D' represents Departure time */
  private char type;
  private double time;

  TrainTimingType(double time, char type) {
   this.time = time;
   this.type = type;
  }

  public char getType() {
   return type;
  }

  public double getTime() {
   return time;
  }

 }

 /**
  * Class represent train time
  */
 public static class TrainTime {
  private double arrival;
  private double departure;

  TrainTime(double arrival, double departure) {
   if (arrival < 0 || departure < 0 || arrival >= 24
     || departure >= 24) {
    throw new IllegalArgumentException(
      "arrival and departutre times are inbetween 0 and 24. arrival : "
        + arrival + " departure : " + departure);
   }
   this.arrival = arrival;
   this.departure = departure;
  }

  public double getArrival() {
   return arrival;
  }

  public double getDeparture() {
   return departure;
  }

 }

 public int getNumberOfPlatForms(List<TrainTime> trainTimes) {
  Objects.nonNull(trainTimes);
  if (trainTimes.size() == 0)
   return 0;

  int count = 0, maxPlatform = Integer.MIN_VALUE;

  List<TrainTimingType> timings = new ArrayList<>();

  for (TrainTime trainTime : trainTimes) {
   timings.add(new TrainTimingType(trainTime.getArrival(), 'A'));
   timings.add(new TrainTimingType(trainTime.getDeparture(), 'D'));
  }

  /* Sort trains based on arrival time */
  Collections.sort(timings, new Comparator<TrainTimingType>() {

   @Override
   public int compare(TrainTimingType train1, TrainTimingType train2) {
    double time = train1.getTime() - train2.getTime();
    if (time > 0)
     return 1;
    else if (time < 0)
     return -1;
    return 0;

   }

  });

  for (TrainTimingType timing : timings) {
   if (timing.getType() == 'A')
    count++;
   else
    count--;

   if (count > maxPlatform)
    maxPlatform = count;
  }

  return maxPlatform;
 }

}