Minimum number of platforms required for a railway station

Question

The problem is as follows: "Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. Trains can arrive before midnight and arrive after midnight"

I understand how the traditional problem works without the condition that trains can arrive before midnight and leave after midnight, as many of the solutions I've seen for this problem doesn't take the midnight condition into account.

My approach was to just use the traditional "Brute Force" method however I considered the trains which arrived before midnight and left after midnight special cases called "Crossover". I've written the following code (in Python), but I'm not entirely certain whether it is the correct approach. For the selected input the code works correctly, but is there any better/more clearer way to approach this problem without using Brute Force?

def findPlatform(arr, dep, n):
    # Crossover means a train arrives before midnight and leaves after midnight
    i = 0
    platmax = 1
    while i < n:
        platforms = 1
        j = i+1
        while j < n:
            # Crossover
            if arr[i] > dep[i]:
                # Crossover
                if ((arr[i] <= arr[j] and arr[i] >= dep[j]) or (arr[j] <= arr[i] and arr[j] >= dep[i])):
                    if arr[j] > dep[i]:
                        platforms += 1
                # Not Crossover
                else:
                    if ((arr[i] <= arr[j] and arr[i] >= dep[j]) or (arr[j] <= arr[i] and arr[j] >= dep[i])):
                        platforms += 1
            # Not Crossover
            else:
                # Crossover
                if arr[j] > dep[j]:
                    if ((arr[i] >= arr[j] and arr[i] >= dep[j]) or (arr[j] >= arr[i] and arr[j] <= dep[i])):
                        platforms += 1
                # Not Crossover
                else:
                    if ((arr[i] >= arr[j] and arr[i] <= dep[j]) or (arr[j] >= arr[i] and arr[j] <= dep[i])):
                        platforms += 1
            j += 1
        if platforms > platmax:
            platmax = platforms
                
        i += 1
    return platmax
# driver code
  
#arr = [900, 940, 950, 1100, 1500, 1800];
#dep = [910, 1120, 1130, 1200, 1900, 2000];
arr = [200, 240, 300, 420, 430, 455, 950, 1130, 2300, 2330, 2340, 2350]
dep = [300, 400, 450, 500, 530, 540, 1150, 1155, 10, 100, 110, 250]
n = len(arr) 
  
print("Minimum Number of Platforms Required = ", 
        findPlatform(arr, dep, n))

Answer 1

This problem reminds me of the classic 'There are 10 passengers in a bus. At first stop, 3 passengers get off and 2 get in. At second stop, 4 passengers get off and 1 get in. At third stop, 1 passenger get out and 5 get in. How many passengers are in the bus?'

This problem is really easy to answer, because you can just keep a count of the number of passengers in the bus, and iterate through the events and adjust the count.

In your problem, instead of passengers in a bus, it's trains in a station. But that doesn't change anything. We can iterate through the events during a 24h period (train arrival, train departure), keep a count of the number of trains in the station, adjust it by +1 at every arrival and -1 at every departure. We also need to keep count of the max number of trains.

One information that we had in the "passengers in a bus" story was the initial number of passengers in the bus. In your problem this translates to "how many trains are in the station at the start of the 24h period", i.e., how many trains arrive before midnight but leave after midnight. Those are exactly the trains whose arrival is "later" than their departure. So we can make a simple function to count these trains:

def get_nb_train_at_midnight(arr, dep):
   return sum(1 for (a,d) in zip(arr,dep) if a > d)

Then we need to iterate through the list of events in order, so let's build that list. An event is a pair (time, type) where type is either 'arr' or 'dep'. We could have made it a triplet (time, type, id) if we also wanted to keep track of which train was currently in the station; but we only care about the number of trains, so we can forget about their id. Let's make a function to build the list of events:

def get_list_of_events(arr, dep):
    events = [(t, 'arr') for t in arr] + [(t, 'dep') for t in dep]
    events.sort()
    return events

Note: we could use the key optional argument to sort to specify we want to sort by time, but time is already the first element in the pair so that's automatic. Also, if we wanted to make triplets with the id of the train, we could write [(t, 'arr', i) for (i, t) in enumerate(arr)] to get the id.

So now we have the list of events in order, and the initial number of trains, so we can iterate through the list of events and keep track of the number of trains in station:

def get_max_nb_trains(events, nb_trains_at_midnight):
    nb_trains = nb_trains_at_midnight
    max_trains = nb_trains
    for (time, type) in events:
        nb_trains += (1 if type == 'arr' else -1)
        max_trains = max(max_trains, nb_trains)
    return max_trains

Let's try those functions in a python repl:

>>> arr = [1,3,7,9,10,10,19,23]
>>> dep = [11,4,11,10,11,2,2,2]
>>> events = get_list_of_events(arr, dep)
>>> nb_trains_midnight = get_nb_train_at_midnight(arr, dep)
>>> events
[(1, 'arr', 0), (2, 'dep', 5), (2, 'dep', 6), (2, 'dep', 7), (3, 'arr', 1), (4, 'dep', 1), (7, 'arr', 2), (9, 'arr', 3), (10, 'arr', 4), (10, 'arr', 5), (10, 'dep', 3), (11, 'dep', 0), (11, 'dep', 2), (11, 'dep', 4), (19, 'arr', 6), (23, 'arr', 7)]
>>> nb_trains_midnight
3
>>> get_max_nb_trains(events, get_nb_train_at_midnight(arr, dep))
5

In this example you can see I did include the ids of the trains in the event list, although that information is not useful.

Answer 2

Test this working code

import java.util.Arrays;

public class TrainsDepArr
{
static int minimumNumberOfPlatform(int array[], int departure[], int n) 
{ 
    Arrays.sort(array); 
    Arrays.sort(departure); 
        
    int plat_needed = 1, maxPlatform = 1; 
        int i = 1, j = 0; 
    
        while (i < n && j < n) { 
        
            if (array[i] <= departure[j]) 
            { 
                plat_needed++; 
            i++; 
                if (plat_needed > maxPlatform) 
            maxPlatform = plat_needed;
            } 
       else if (array[i] > departure[j]) { 
                plat_needed--; 
                j++; 
            } 
             
    } 

        return maxPlatform; 
    } 
    public static void main(String[] args)
{
   int[] arrival = { 100, 140, 150, 200, 215, 400 };
        int[] departure = {110, 300, 220, 230, 315, 600};
         int n = arrival.length; 

    System.out.print("Minimum platforms required is "
                    + minimumNumberOfPlatform(arrival, departure,n));
}
}