Minimum number of platforms required for a railway

Intuition

Consider each train's schedule and see how many other trains are at the station at the same time. For each train, compare its arrival and departure times with those of all other trains to find overlaps. Count how many trains are at the station simultaneously and keep track of the highest number you find.

Approach

Start by setting an initial count to one, assuming that at least one platform is needed.
Loop through each train's arrival time to check how many other trains are at the station simultaneously, one by one.
For each train, start a counter at one to include the current train itself, keeping track of how many trains overlap with it.
Within the loop for each train, compare it with all subsequent trains to check if their schedules overlap with the current train's schedule.
During these comparisons, check if the current train’s arrival and departure times overlap with those of the subsequent trains. If they do, increment the counter.
After counting overlaps for the current train, update the initial count to reflect the highest number of overlapping trains found, ensuring you are tracking the maximum number of platforms needed.
After looping through all trains and checking overlaps, the highest count will be the minimum number of platforms required to ensure no train has to wait.

Dry Run

Counting of Overlapping Trains

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find minimum number of platforms required
    int findPlatform(vector<int>& Arrival, vector<int>& Departure) {
        int n = Arrival.size();
        
        // To store the result
        int ans = 1;

        // Iterate on the trains platforms
        for (int i = 0; i < n; i++) {
            
            int count = 1;

            // Iterate on the all the trains 
            for (int j = 0; j < n; j++) {
                // Check with other trains
                if(i != j) {

                    // Check for the overlapping trains 
                    if ((Arrival[i] >= Arrival[j] && Departure[j] >= Arrival[i])) {
                        // Increment count
                        count++;
                    }
                    
                    
                    // Update the minimum platforms needed
                    ans = max(ans, count);
                }
            }
        }

        // Return number of platforms
        return ans;
    }
};

int main() {
    vector<int> arr = {900, 945, 955, 1100, 1500, 1800};
    vector<int> dep = {920, 1200, 1130, 1150, 1900, 2000};
    
    int n = dep.size();
    
    // Creating an instance of Solution class
    Solution sol;
    
    // Function call to find minimum number of platforms required
    int ans = sol.findPlatform(arr, dep);
    
    cout << "Minimum number of Platforms required: " << ans << endl;
}
class Solution {
    // Function to find minimum number of platforms required
    public int findPlatform(int[] Arrival, int[] Departure) {
        int n = Arrival.length;

        // To store the result
        int ans = 1;

        // Iterate on the trains platforms
        for (int i = 0; i < n; i++) {
            
            int count = 1;

            // Iterate on all the trains 
            for (int j = 0; j < n; j++) {
                // Check with other trains
                if (i != j) {

                    // Check for the overlapping trains 
                    if ((Arrival[i] >= Arrival[j] && Departure[j] >= Arrival[i])) {
                        // Increment count
                        count++;
                    }

                    // Update the minimum platforms needed
                    ans = Math.max(ans, count);
                }
            }
        }

        // Return number of platforms
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int[] arr = {900, 945, 955, 1100, 1500, 1800};
        int[] dep = {920, 1200, 1130, 1150, 1900, 2000};

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to find minimum number of platforms required
        int ans = sol.findPlatform(arr, dep);

        System.out.println("Minimum number of Platforms required: " + ans);
    }
}
class Solution:
    # Function to find minimum number of platforms required
    def findPlatform(self, Arrival, Departure):
        n = len(Arrival)

        # To store the result
        ans = 1

        # Iterate on the trains platforms
        for i in range(n):
            
            count = 1

            # Iterate on all the trains 
            for j in range(n):
                # Check with other trains
                if i != j:

                    # Check for the overlapping trains 
                    if Arrival[i] >= Arrival[j] and Departure[j] >= Arrival[i]:
                        # Increment count
                        count += 1

                    # Update the minimum platforms needed
                    ans = max(ans, count)

        # Return number of platforms
        return ans


if __name__ == "__main__":
    arr = [900, 945, 955, 1100, 1500, 1800]
    dep = [920, 1200, 1130, 1150, 1900, 2000]

    # Creating an instance of Solution class
    sol = Solution()

    # Function call to find minimum number of platforms required
    ans = sol.findPlatform(arr, dep)

    print("Minimum number of Platforms required:", ans)
class Solution {
    // Function to find minimum number of platforms required
    findPlatform(Arrival, Departure) {
        let n = Arrival.length;

        // To store the result
        let ans = 1;

        // Iterate on the trains platforms
        for (let i = 0; i < n; i++) {
            
            let count = 1;

            // Iterate on all the trains 
            for (let j = 0; j < n; j++) {
                // Check with other trains
                if (i !== j) {

                    // Check for the overlapping trains 
                    if (Arrival[i] >= Arrival[j] && Departure[j] >= Arrival[i]) {
                        // Increment count
                        count++;
                    }

                    // Update the minimum platforms needed
                    ans = Math.max(ans, count);
                }
            }
        }

        // Return number of platforms
        return ans;
    }
}

// Main execution
const arr = [900, 945, 955, 1100, 1500, 1800];
const dep = [920, 1200, 1130, 1150, 1900, 2000];

// Creating an instance of Solution class
const sol = new Solution();

// Function call to find minimum number of platforms required
const ans = sol.findPlatform(arr, dep);

console.log("Minimum number of Platforms required:", ans);

Complexity Analysis

Time Complexity: O(N^2) where N is the number of trains. This is because the code uses a nested loop structure: the outer loop iterates through each train's arrival time, and for each iteration of the outer loop, the inner loop checks for overlapping intervals with all other trains. Each iteration of the inner loop involves constant-time comparison operations. Still, since the inner loop runs N times for each N iterations of the outer loop, the total number of operations is N X N, leading to a quadratic time complexity. Space Complexity : O(1) because no extra space is used.

Intuition

Start by sorting both the arrival and departure times. Once these times are sorted, it becomes much easier to keep track of the trains currently at the station. By moving through these sorted times, we can count how many trains have arrived but not yet departed at any given moment. The difference between the number of arrivals and departures at each point will tell us how many platforms are needed at that time. The highest number of platforms required during these times gives us the final answer.

Approach

Start by sorting both the arrival and departure arrays. Sorting helps in managing the train schedules efficiently.
Initialize two pointers, one for the arrival array and one for the departure array. These pointers will help in traversing both arrays simultaneously.
Also, initialize two variables to keep track of the count of platforms needed at any time and the maximum number of platforms needed.
Use a loop to iterate through the arrival and departure times. Compare the current arrival time with the current departure time using the two pointers.
If the arrival time is less than or equal to the departure time, it means a train has arrived before the earliest train has departed, so increment the count of platforms needed and move the arrival pointer to the next train.
If the arrival time is greater than the departure time, it means a train has departed, freeing up a platform. Decrement the count of platforms needed and move the departure pointer to the next train.
After each comparison, update the maximum number of platforms needed if the current count exceeds the previous maximum.
Continue this process until you have processed all trains, then return the maximum number of platforms needed, which will be the final answer.

Dry Run

Optimally sorting of arrival and departure time

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
//  To find number of platforms
    int findPlatform(vector<int>& Arrival, vector<int>& Departure) {
        int n = Arrival.size();
        
        // Sort both arrival and departure arrays
        sort(Arrival.begin(), Arrival.end());
        sort(Departure.begin(), Departure.end());

        int ans = 1;
        int count = 1;
        int i = 1, j = 0;
        
        // Iterate through the arrays
        while (i < n && j < n) {
            if (Arrival[i] <= Departure[j]) {
                // Increment count
                count++;
                i++;
            } else {
                // Decrement Count
                count--;
                j++;
            }
            // Find maximum
            ans = max(ans, count);
        }
        return ans;
    }
};

int main() {
    vector<int> arr = {900, 945, 955, 1100, 1500, 1800};
    vector<int> dep = {920, 1200, 1130, 1150, 1900, 2000};
    
    Solution sol;
    cout << "Minimum number of Platforms required: " << sol.findPlatform(arr, dep) << endl;
}
import java.util.*;

class Solution {
//  To find number of platforms
    public int findPlatform(int[] Arrival, int[] Departure) {
        int n = Arrival.length;

        // Sort both arrival and departure arrays
        Arrays.sort(Arrival);
        Arrays.sort(Departure);

        int ans = 1;
        int count = 1;
        int i = 1, j = 0;

        // Iterate through the arrays
        while (i < n && j < n) {
            if (Arrival[i] <= Departure[j]) {
                // Increment count
                count++;
                i++;
            } else {
                // Decrement count
                count--;
                j++;
            }
            // Find maximum
            ans = Math.max(ans, count);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {900, 945, 955, 1100, 1500, 1800};
        int[] dep = {920, 1200, 1130, 1150, 1900, 2000};

        Solution sol = new Solution();
        System.out.println("Minimum number of Platforms required: " + sol.findPlatform(arr, dep));
    }
}
class Solution:
     #  To find number of platforms
    def findPlatform(self, Arrival, Departure):
        n = len(Arrival)

        # Sort both arrival and departure arrays
        Arrival.sort()
        Departure.sort()

        ans = 1
        count = 1
        i, j = 1, 0

        # Iterate through the arrays
        while i < n and j < n:
            if Arrival[i] <= Departure[j]:
                # Increment count
                count += 1
                i += 1
            else:
                # Decrement count
                count -= 1
                j += 1
            # Find maximum
            ans = max(ans, count)
        return ans

# Test the solution
arr = [900, 945, 955, 1100, 1500, 1800]
dep = [920, 1200, 1130, 1150, 1900, 2000]

solution = Solution()
print("Minimum number of Platforms required:", solution.findPlatform(arr, dep))
class Solution {
//  To find number of platforms
    findPlatform(Arrival, Departure) {
        let n = Arrival.length;

        // Sort both arrival and departure arrays
        Arrival.sort((a, b) => a - b);
        Departure.sort((a, b) => a - b);

        let ans = 1;
        let count = 1;
        let i = 1, j = 0;

        // Iterate through the arrays
        while (i < n && j < n) {
            if (Arrival[i] <= Departure[j]) {
                // Increment count
                count++;
                i++;
            } else {
                // Decrement count
                count--;
                j++;
            }
            // Find maximum
            ans = Math.max(ans, count);
        }
        return ans;
    }
}

// Test the solution
let arr = [900, 945, 955, 1100, 1500, 1800];
let dep = [920, 1200, 1130, 1150, 1900, 2000];

let solution = new Solution();
console.log("Minimum number of Platforms required:", solution.findPlatform(arr, dep));

Complexity Analysis

Time Complexity: O(N log N) where N is the size of each array.This is primarily due to the sorting operations on the arrival and departure arrays, each taking O(N log N). The subsequent traversal of the arrays using the two-pointer technique takes O(N), but this does not affect the overall complexity, which is dominated by the sorting step. Therefore, the combined time complexity remains O(N log N). Space Complexity: O(1) as no extra space is used.

Problem List

Minimum number of platforms required for a railway

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code