Problem Statement
You are building a railway station. Numerous trains will arrive at and depart from your station, and your station must be able to accept them all. You want to occupy as small an area as possible, thus you don't want to build unnecessary platforms for people to load and unload from. Also, you've decided to make your station one-way - so trains will all depart and arrive going in the same direction.
You will be given a full timetable for the station. A int[] arrival and a int[] departure give you arrival and departure times for all trains (the ith element of arrival corresponds to the ith element of departure). Each platform may only service one train at a time. Hence, when a train arrives at a particular platform, it must wait until all the trains that arrived at that platform before it have already departed. Therefore, if train A arrives before train B, but leaves after train B, the two trains may not use the same platform. If they used the same platform, train B would have to wait until train A departed before it could depart, and this would cause train B to depart later than its scheduled time.
Your program should return an int - the minimal number of platforms your station can have so that every train may arrive at some platform at its arrival time, and then depart from that platform at the departure time.
For example, if arrival = {1, 2, 5, 11, 6} and departure = {10, 20, 12, 22, 21} we only need two platforms. Trains 0, 2 and 3 will use one platform, while trains 1 and 4 will use the other.
You will be given a full timetable for the station. A int[] arrival and a int[] departure give you arrival and departure times for all trains (the ith element of arrival corresponds to the ith element of departure). Each platform may only service one train at a time. Hence, when a train arrives at a particular platform, it must wait until all the trains that arrived at that platform before it have already departed. Therefore, if train A arrives before train B, but leaves after train B, the two trains may not use the same platform. If they used the same platform, train B would have to wait until train A departed before it could depart, and this would cause train B to depart later than its scheduled time.
Your program should return an int - the minimal number of platforms your station can have so that every train may arrive at some platform at its arrival time, and then depart from that platform at the departure time.
For example, if arrival = {1, 2, 5, 11, 6} and departure = {10, 20, 12, 22, 21} we only need two platforms. Trains 0, 2 and 3 will use one platform, while trains 1 and 4 will use the other.
Definition
- Class:
- Station
- Method:
- minimalWays
- Parameters:
- int[], int[]
- Returns:
- int
- Method signature:
- int minimalWays(int[] arrival, int[] departure)
- (be sure your method is public)
Constraints
- arrival and departure will contain between 2 and 10 elements, inclusive.
- arrival and departure will contain the same number of elements.
- Each element of arrival and departure will be between 1 and 100, inclusive.
- Each element of arrival and departure will be distinct (no integer in arrival will also be in departure and no integer will appear more than once in either int[]).
Examples
{1, 5, 3, 2}{6, 10, 8, 7}Returns: 1
We need only 1 platform since the trains depart in the same order they arrive.{1, 2, 5, 11, 6}{10, 20, 12, 22, 21}Returns: 2
The example in the problem statement.{1,2,3,4,5,6,7,8,9,10}{11,12,13,14,15,16,17,18,19,20}Returns: 1
{45,32,14,39,54,38,27}{16,43,96,10,31,58,77}Returns: 4
Back to all problems