How to calculate the minimum number of platforms required for railway or bus stations?

Here the task is to find out minimum number of platforms required for the railway station so that no trains are wait. So, given arrival and departure times of all trains that reach a railway station.

Now we are given two arrays which represents arrival and departure times of trains that stop.

Example:

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 (platforms needed)
Explantion: Only 3 platforms are required

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

Native Solution:

The idea is to take every interval one by one and find number of intervals that overlap with it.

By tracking 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.

Now implementation through coding:

C++ Program to find the minimum number of platforms required on a railway station

// Program to find minimum number of platforms
// required on a railway station
#include <algorithm>
#include <iostream>

using namespace std;

// Returns minimum number of platforms reqquired
int findPlatform(int arr[], int dep[], int n)
{

	// plat_needed indicates number of platforms
	// needed at a time
	int plat_needed = 1, result = 1;
	int i = 1, j = 0;

	// run a nested loop to find overlap
	for (int i = 0; i < n; i++) {
		// minimum platform
		plat_needed = 1;

		for (int j = i + 1; j < n; j++) {
			// check for overlap
			if ((arr[i] >= arr[j] && arr[i] <= dep[j]) ||
		(arr[j] >= arr[i] && arr[j] <= dep[i]))
				plat_needed++;
		}

		// update result
		result = max(result, plat_needed);
	}

	return result;
}

// Driver Code
int main()
{
	int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
	int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << "Minimum Number of Platforms Required = "
		<< findPlatform(arr, dep, n);
	return 0;
}

Java Program to find the minimum number of platforms required on a railway station

// Program to find minimum number of platforms
// required on a railway station
import java.io.*;

class GFG {
	// Returns minimum number of platforms reqquired
	public static int findPlatform(int arr[], int dep[],
								int n)
	{

		// plat_needed indicates number of platforms
		// needed at a time
		int plat_needed = 1, result = 1;
		int i = 1, j = 0;

		// run a nested loop to find overlap
		for (i = 0; i < n; i++) {
			// minimum platform
			plat_needed = 1;

			for (j = i + 1; j < n; j++) {
				// check for overlap
				if ((arr[i] >= arr[j] && arr[i] <= dep[j])
					|| (arr[j] >= arr[i]
						&& arr[j] <= dep[i]))
					plat_needed++;
			}

			// update result
			result = Math.max(result, plat_needed);
		}

		return result;
	}

	// Driver Code
	public static void main(String[] args)
	{
		int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
		int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
		int n = 6;
		System.out.println(
			"Minimum Number of Platforms Required = "
			+ findPlatform(arr, dep, n));
	}
}

Output:

Minimum Number of Platforms Required = 3

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.

Effective Solution:

The idea is to consider all trains time in sorted order. Once the trains time is 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
 9:10       Departure                0
 9:40       Arrival                  1
 9:50       Arrival                  2
 11:00      Arrival                  3 
 11:20      Departure                2
 11:30      Departure                1
 12:00      Departure                0
 15:00      Arrival                  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

So, This approach assumes that trains are arriving and departing on the same date. 

Algorithm:

  1. Sort the arrival and departure time of trains.
  2. Create two pointers i=0, and j=0 and a variable to store ans and current count plat
  3. Run a loop while i<n and j<n and compare the ith element of arrival array and jth element of departure array.
  4. if the arrival time is less than or equal to departure then one more platform is needed so increase the count, i.e. plat++ and increment i
  5. Else if the arrival time greater than departure then one less platform is needed so decrease the count, i.e. plat– and increment j
  6. Update the ans, i.e ans = max(ans, plat).

Implementation: This doesn’t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses merge process of merge sort to process them together as a single sorted array. 

C++ program to find the minimum number of platforms required on a railway station

// Program to find minimum number of platforms
// required on a railway station
#include <algorithm>
#include <iostream>

using namespace std;

// Returns minimum number of platforms reqquired
int findPlatform(int arr[], int dep[], int n)
{
	// Sort arrival and departure arrays
	sort(arr, arr + n);
	sort(dep, dep + n);

	// plat_needed indicates number of platforms
	// needed at a time
	int plat_needed = 1, result = 1;
	int i = 1, j = 0;

	// Similar to merge in merge sort to process
	// all events in sorted order
	while (i < n && j < n) {
		// If next event in sorted order is arrival,
		// increment count of platforms needed
		if (arr[i] <= dep[j]) {
			plat_needed++;
			i++;
		}

		// Else decrement count of platforms needed
		else if (arr[i] > dep[j]) {
			plat_needed--;
			j++;
		}

		// Update result if needed
		if (plat_needed > result)
			result = plat_needed;
	}

	return result;
}

// Driver code
int main()
{
	int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
	int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << "Minimum Number of Platforms Required = "
		<< findPlatform(arr, dep, n);
	return 0;
}

Java program to find the minimum number of platforms required on a railway station

// Program to find minimum number of platforms

import java.util.*;

class GFG {

	// Returns minimum number of platforms reqquired
	static int findPlatform(int arr[], int dep[], int n)
	{
		// Sort arrival and departure arrays
		Arrays.sort(arr);
		Arrays.sort(dep);

		// plat_needed indicates number of platforms
		// needed at a time
		int plat_needed = 1, result = 1;
		int i = 1, j = 0;

		// Similar to merge in merge sort to process
		// all events in sorted order
		while (i < n && j < n) {
			// If next event in sorted order is arrival,
			// increment count of platforms needed
			if (arr[i] <= dep[j]) {
				plat_needed++;
				i++;
			}

			// Else decrement count of platforms needed
			else if (arr[i] > dep[j]) {
				plat_needed--;
				j++;
			}

			// Update result if needed
			if (plat_needed > result)
				result = plat_needed;
		}

		return result;
	}

	// Driver code
	public static void main(String[] args)
	{
		int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
		int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
		int n = arr.length;
		System.out.println("Minimum Number of Platforms Required = "
						+ findPlatform(arr, dep, n));
	}
}

Python3 program to find the minimum number of platforms required on a railway station

# Program to find minimum
# number of platforms
# required on a railway
# station

# Returns minimum number
# of platforms reqquired


def findPlatform(arr, dep, n):

	# Sort arrival and
	# departure arrays
	arr.sort()
	dep.sort()

	# plat_needed indicates
	# number of platforms
	# needed at a time
	plat_needed = 1
	result = 1
	i = 1
	j = 0

	# Similar to merge in
	# merge sort to process
	# all events in sorted order
	while (i < n and j < n):

		# If next event in sorted
		# order is arrival,
		# increment count of
		# platforms needed
		if (arr[i] <= dep[j]):

			plat_needed += 1
			i += 1

		# Else decrement count
		# of platforms needed
		elif (arr[i] > dep[j]):

			plat_needed -= 1
			j += 1

		# Update result if needed
		if (plat_needed > result):
			result = plat_needed

	return result

# Driver code


arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arr)

print("Minimum Number of Platforms Required = ",
	findPlatform(arr, dep, n))

# This code is contributed
# by Anant Agarwal.

C# program to find the minimum number of platforms required on a railway station

// C# program to find minimum number
// of platforms
using System;

class GFG {

	// Returns minimum number of platforms
	// reqquired
	static int findPlatform(int[] arr, int[] dep, int n)
	{

		// Sort arrival and departure arrays
		Array.Sort(arr);
		Array.Sort(dep);

		// plat_needed indicates number of
		// platforms needed at a time
		int plat_needed = 1, result = 1;
		int i = 1, j = 0;

		// Similar to merge in merge sort
		// to process all events in sorted
		// order
		while (i < n && j < n) {

			// If next event in sorted order
			// is arrival, increment count
			// of platforms needed
			if (arr[i] <= dep[j])
			{
				plat_needed++;
				i++;
			}

			// Else decrement count of
			// platforms needed
			else if (arr[i] > dep[j])
			{
				plat_needed--;
				j++;
			}

			// Update result if needed
			if (plat_needed > result)
				result = plat_needed;
		}

		return result;
	}

	// Driver code
	public static void Main()
	{
		int[] arr = { 900, 940, 950, 1100, 1500, 1800 };
		int[] dep = { 910, 1200, 1120, 1130, 1900, 2000 };
		int n = arr.Length;
		Console.Write("Minimum Number of "
					+ " Platforms Required = "
					+ findPlatform(arr, dep, n));
	}
}

// This code os contributed by nitin mittal.

PHP program to find the minimum number of platforms required on a railway station

<?php
// PHP Program to find minimum number
// of platforms required on a railway
// station

// Returns minimum number of
// platforms reqquired
function findPlatform($arr, $dep, $n)
{
	
	// Sort arrival and
	// departure arrays
	sort($arr);
	sort($dep);
	
	// plat_needed indicates
	// number of platforms
	// needed at a time
	$plat_needed = 1;
	$result = 1;
	$i = 1;
	$j = 0;
	
	// Similar to merge in
	// merge sort to process
	// all events in sorted order
	while ($i < $n and $j < $n)
	{
		
		// If next event in sorted
		// order is arrival, increment
		// count of platforms needed
		if ($arr[$i] <= $dep[$j])
		{
			$plat_needed++;
			$i++;
		}
	
		// Else decrement count
		// of platforms needed
		elseif ($arr[$i] > $dep[$j])
		{
			$plat_needed--;
			$j++;
		}

		// Update result if needed
		if ($plat_needed > $result)
			$result = $plat_needed;
	}
	
	return $result;
}

	// Driver Code
	$arr = array(900, 940, 950, 1100, 1500, 1800);
	$dep = array(910, 1200, 1120, 1130, 1900, 2000);
	$n = count($arr);
	echo "Minimum Number of Platforms Required = ", findPlatform($arr, $dep, $n);

// This code is contributed by anuj_67.
?>

Output

Minimum number of platforms required = 3

Complexity Analysis: 

  • Time Complexity: O(nlogn). 
    One traversal O(n) of both the array is needed after sorting O(nlogn), so the time complexity is O(nlogn).
  • Space Complexity: O(1). 
    As no extra space is required.

Please write about the article if you get anything incorrect, or you want to add more information about this topic discussed above through WhatsApp me.

Share Your Love
Default image
Lingaraj Senapati
Hey There! I am Lingaraj Senapati, the Co-founder of lingarajtechhub.com My skills are Freelance, Web Developer & Designer, Corporate Trainer, Digital Marketer & Youtuber.
Articles: 73

Newsletter Updates

Enter your email address below to subscribe to our newsletter

Leave a Reply