Q$2.[20$ pts$]$ Minimum Number of Platforms Required

Problem Statement:

You are the station manager at a busy railway station and need to ensure that there are enough platforms to accommodate all arriving and departing trains without causing delays. Each train has a scheduled arrival and departure time. If two trains overlap $($one arrives before another departs$),$ they cannot share the same platform.

Note: Platform area is the area where trains arrive and depart, and passengers can board or alight from the train.

Your task is to determine the minimum number of platforms required at any time to handle all trains without delay.

Input:

An integer array arr$[]$ of size $n,$ where arr$[$i$]$ is the arrival time of the $i^{th}$ train.

An integer array dep$[]$ of size n $,$ where dep$[$i$]$ is the departure time of the ith train.

Times are given in a $24-$hour format $($e$.$g$.,900$ for $9$:$00$ AM$,1330$ for $1$:$30$ PM$).$

Output:

An integer represents the minimum number of platforms required.

CpE $300$ Design and Analysis of Algorithms

Fall $2024$

Sample Output:At the peak of train arrivals and departures $($between $950$ and $1130),$ three platforms are needed simultaneously.Please Answer and submit the following:

Describe the Greedy Choice: Explain the decision$-$making process you use at each step $($e$.$g$.,$ sorting arrival and departure times, incrementing platforms on arrival, decrementing on departure$).$

Explain the Optimal Substructure: Explain how solving the subproblems $($tracking arrivals and departures$)$ leads to an optimal solution for the entire schedule.

Data Structures and Complexity: Identify the data structures used in your solution and provide the time and space complexity.

Write the Code in Java: Implement the solution in Java$/$python$.$ Submit a $.$java$/.$py file that includes a sample run as a comment at the end of the file. Your code should efficiently compute the minimum number of platforms required to accommodate any given set of train schedules without delays.