Table of Contents
If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Problem:
You are given arrival and departure time of trains reaching to a particular station. You need to find minimum number of platforms required to accommodate the trains at any point of time.
For example:
|
1 2 3 4 5 |
arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00} departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00} No. of platforms required in above scenario = 4 |
Please note that arrival time is in chronological order.
Solution :
If you notice we need to find maximum number of trains that can be on the station with the help of arrival and departure time.
Solution 1:
You can iterate over all intervals and check how many other intervals are overlapping with it but that will require o(N^2) time complexity.
Solution 2:
We will use logic very much similar to merge sort.
- Sort both arrival(arr) and departure(dep) arrays.
- Compare current element in arrival and departure array and pick smaller one among both.
- If element is pick up from arrival array then increment platform_needed.
- If element is pick up from departure array then decrement platform_needed.
- While performing above steps, we need track count of maximum value reached for platform_needed.
- In the end, we will return maximum value reached for platform_needed.
Time complexity : O(NLogN)
Below diagram will make you understand above code better:
Java program for Minimum number of platform required for a railway station
|
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 |
package org.arpit.java2blog; import java.util.Arrays; public class TrainPlatformMain { public static void main(String args[]) { // arr[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00} // dep[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00} int arr[] = {100, 140, 150, 200, 215, 400}; int dep[] = {110, 300, 210, 230,315, 600}; System.out.println("Minimum platforms needed:"+findPlatformsRequiredForStation(arr,dep,6)); } static int findPlatformsRequiredForStation(int arr[], int dep[], int n) { int platform_needed = 0, maxPlatforms = 0; Arrays.sort(arr); Arrays.sort(dep); int i = 0, j = 0; // Similar to merge in merge sort while (i < n && j < n) { if (arr[i] < dep[j]) { platform_needed++; i++; if (platform_needed > maxPlatforms) maxPlatforms = platform_needed; } else { platform_needed--; j++; } } return maxPlatforms; } } |
|
1 2 3 |
Minimum platforms needed:4 |
