educative.io

Educative

Binary sort solution issue

As we are separately sorting both the arrival and destination time arrays, it is possible that the sequence is not preserved in its respective order.

For eg -
Input

Arrival [900, 940, 950, 1100, 1500, 1800]
Departure [910, 1200, 1120, 1130, 1900, 2000]

After individual sorting, the sequence of departure will get updated while the sequence of arrival remains the same and hence we loose the original mappings.

So, it should be better to sort both the arrays at the same time while zipping them.

My solution -

def find_platform(arrival, departure):
    """
    Finds the minimum number of platforms required for a railway Station
    :param arrival: A list of arrival Timing
    :param departure: A list of departure Timing
    :return: Minimum number of platforms required for a railway Station
    """

    # Keeping track of the platforms
    max_platforms = 0
    trains_queue = []

    # Sorting and looping over arrivals and departures
    # Sorting takes place entirely on the arrivals (and departure, if two arrivals are same) and same sequence is followed for departure.
    for arr, dep in sorted(zip(arrival, departure), key = lambda x: (x[0], x[1])):

        # Removing all past trains from queue who have departed before current train arrived
        while trains_queue and trains_queue[0][1] <= arr:
            trains_queue.pop(0)

        # Adding current train to the queue
        trains_queue.append([arr, dep])

        # Updating the number of platforms, which are needed to cater all the trains
        if len(trains_queue) > max_platforms:
            max_platforms = len(trains_queue)

    # Returning the result
    return max_platforms