The Question
Coding

Minimum Number of Railway Platforms

Given two arrays representing the arrival and departure times of all trains reaching a station, calculate the minimum number of platforms required so that no train is kept waiting. Constraints and Details: 1. All trains arrive and depart on the same day. 2. Times are provided in 24-hour format (HHMM). 3. If a train arrives at the same time another train departs, they cannot share the same platform; a separate platform is required for the arriving train. 4. Input arrays Arrival and Departure are of size $N$. Example: Input: Arrival = [900, 940, 950, 1100, 1500, 1800], Departure = [910, 1200, 1120, 1130, 1900, 2000] Output: 3
C++
Two-Pointer
Greedy
Sorting
Questions & Insights

Clarifying Questions

What is the maximum size of the input arrays? (Assuming up to 10^5 elements, which necessitates an O(N \log N) solution).
Can a train depart exactly when another arrives? The problem states: "the same platform cannot be used for both the departure of one train and the arrival of another train." This implies if Arrival[i] == Departure[j], two platforms are required at that specific moment.
Is it possible for a departure time to be earlier than an arrival time for the same train? Given the "same day" constraint, we assume Departure[i] > Arrival[i] for all i.
Are the arrival and departure arrays sorted initially? Usually, they are not, so sorting will be a required step.

Thinking Process

View as Events: Treat every arrival and departure as an event. An arrival increases the platform demand by 1, and a departure decreases it by 1.
Chronological Processing: To find the maximum demand at any point, we must process all events in chronological order. Even though arrivals and departures are paired in the input, their specific pairing doesn't matter for the total platform count; only the times they occur do.
Strict Constraint Handling: Because a platform cannot be reused at the exact same time a train leaves (per the prompt), an arrival occurring at time T must be processed before a departure occurring at time To ensure we calculate the peak occupancy correctly.
Two-Pointer Strategy: Sort both arrays. Use one pointer for arrivals and one for departures. Iterate through time, incrementing the count for arrivals and decrementing for departures, while maintaining a global maximum.
Implementation Breakdown

Problem Set

Functional Requirements: Return an integer representing the minimum number of platforms.
Constraints:
Time: O(N \log N) due to sorting.
Space: O(1) extra space (if sorting in-place) or O(N) (if inputs must be preserved).

Approach

Algorithm: Two-Pointer / Greedy Sweep-line.
Data Structure: Array.
Complexity: Time O(N \log N), Space O(1) (in-place).

Implementation

Wrap Up

Advanced Topics

Readability vs Performance: While sorting in-place is O(1) space, in a real-world production system, we would likely copy the data to avoid side effects on the input parameters (favoring immutability).
Alternative Algorithm (Frequency Array): Since the time is constrained to HHMM (0000 to 2359), we could use a frequency array of size 2400. We mark +1 at arrival and -1 at departure + 1. This would be O(N + \text{Range}), making it O(N) effectively if N is large.
Handling Multi-day Schedules: If trains could arrive one day and leave the next, we would need to check if Departure[i] < Arrival[i]. In such cases, we would essentially be dealing with a circular timeline or simply splitting the interval into two (start to end-of-day and start-of-day to departure).