# 1. Thinking Process - **View as Global Event Stream**: The problem asks for the maximum number of concurrent events. Since we only need the count, we can treat arrivals and departures as independent events sorted in chronological order. - **Two-Pointer/Sweep-Line Strategy**: By sorting both arrival and departure arrays independently, we can use two pointers to simulate time. An arrival increases the platform count, and a departure decreases it. - **Handling Simultaneous Events**: The requirement states that if an arrival and departure occur at the exact same time, they cannot share a platform. To handle this, we treat the arrival as occurring "before" the departure frees the platform (i.e., if `arrival[i] <= departure[j]`, we increment the platform count). - **Optimization**: Sorting takes $O(N \log N)$, and the single pass with two pointers takes $O(N)$. This is efficient for constraints up to $10^5$ or $10^6$ trains. # 2. Problem set - **Functional Requirements**: Find the minimum number of platforms required to prevent any train from waiting. - **Constraints**: - Input times are in HHMM format (0-2359). - If arrival time = departure time, an extra platform is required. - Trains arrive and depart on the same day. - **Example 1**: Arrival `[900, 940, 950, 1100, 1500, 1800]`, Departure `[910, 1200, 1120, 1130, 1900, 2000]`. Output: `3`. - **Example 2**: Arrival `[900, 1100, 1235]`, Departure `[1000, 1200, 1240]`. Output: `1`. # 3. Methodology - **Algorithm**: Sorting + Two Pointers (Sweep Line). - **Data Structure**: Two arrays/vectors to store and sort times. - **Complexity**: - Time: $O(N \log N)$ due to sorting. - Space: $O(1)$ if sorting is done in-place, or $O(N)$ for local copies. # 4. Solution ```cpp #include #include #include /** * Calculates the minimum number of platforms required. * @param arr Array of arrival times * @param dep Array of departure times * @param n Number of trains * @return Minimum platforms needed */ int findPlatform(int arr[], int dep[], int n) { // 1. Sort both arrival and departure arrays independently. // The relationship between a specific train's arrival and departure doesn't matter // for calculating the maximum overlap at any point in time. std::sort(arr, arr + n); std::sort(dep, dep + n); // 2. Initialize pointers and counters. int platforms_needed = 0; int max_platforms = 0; int i = 0; // Pointer for arrival array int j = 0; // Pointer for departure array // 3. Sweep through the timeline using two pointers. while (i < n && j < n) { // If a train arrives before or at the same time another departs, // we need an additional platform. // The "==" condition handles the requirement: "same platform cannot be // used for both departure and arrival at the same time". if (arr[i] <= dep[j]) { platforms_needed++; i++; } // If a train departs before the next one arrives, a platform is freed. else { platforms_needed--; j++; } // Update the maximum platforms encountered so far. if (platforms_needed > max_platforms) { max_platforms = platforms_needed; } } return max_platforms; } int main() { // Example 1 int arrival1[] = {900, 940, 950, 1100, 1500, 1800}; int departure1[] = {910, 1200, 1120, 1130, 1900, 2000}; int n1 = sizeof(arrival1) / sizeof(arrival1[0]); std::cout << "Example 1 Platforms: " << findPlatform(arrival1, departure1, n1) << std::endl; // Example 2 int arrival2[] = {900, 1100, 1235}; int departure2[] = {1000, 1200, 1240}; int n2 = sizeof(arrival2) / sizeof(arrival2[0]); std::cout << "Example 2 Platforms: " << findPlatform(arrival2, departure2, n2) << std::endl; return 0; } ```