3
$\begingroup$

The questions is as follows with the answer:

Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to wait for another train to vacate the platform. The question basically means calculate the maximum number of trains that would be present in the platform at any given time.

Answer

Sort the arrival time and sort the departure time, keep a count initialized to 0. compare the first element of the arrival time with the first of departure, increase the value of count if the value at current Index at arrival is less than the value index at departure and increment the arrival index, and vice versa. Keep the maximum count that you see.

MY PROBLEM: I have tried hard but I am not able to get why to sort both arrival and departure timings? As a train is single entity and you sort arrival and departure separately how can we know which train arrival matches with its departure? I am facing the same problem in closest pair problem as why to sort x points and y points separately.

$\endgroup$
1
$\begingroup$

The answer is very simple: try to construct an algorithm which doesn't sort both arrival and departure times, and see if that's possible. If so, then there is an alternative algorithm which indeed doesn't requiring both times. Otherwise, you will understand why this is necessary.

The intuitive explanation of why we sort both arrival and departure times is that we are actually sorting all events. There are two types of events, arrival and departure, and we want to process them as they happen. We don't care about matching departure times with arrival times – that is, for our algorithm to work, we don't need to know which train is involved, only that a train has arrived or has left the station.

This actually suggests a way to restate the algorithm you describe. Sort all events according to time. Now go over them in order of increasing time (we assume for simplicity that all times are distinct). Keep a counter of the number of trains in station. When processing an arrival event, increase the counter; when processing a departure event, decrease the counter. Keep track of the maximal value of the counter.

The algorithm you describe instead sorts the arrival and departure times separately, and then performs an online merge (same algorithm as in merge sort for merging two sorted lists). I don't know why they described the algorithm this way rather than the way I described it.

$\endgroup$
-1
$\begingroup$
  • Create a single timeline in which an arrival is a +1 and a departure is a -1 (train)

  • Then sort on that single time

  • Your don't really care which train is at the station but rather a train

  • When a train arrives +1

  • When a train depart -1

  • Keep a running total of the trains at the platform / station

If have

arrival depart  
1       3
2       4 

Then at time 2 there will 2 trains at the station
And at time 3 then will be 1 train at the station
Must sort on arrival/depart to sync on the two events

I am not good with pseudocode

foreach (stop in schedule)
{
    timeline.add(stop.station, +1, stop.arrivalTime) 
    timeline.add(stop.station, -1, stop.Departure time) 
}

int maxTrains = 0 
int trains = 0 
foreach (tlStop in in timeline.where(tlStop.station = x).orderby(tlStop.time))
{
    trains += tlStop.arriveDepart 
    if(maxTrains < trains)
       maxTrains = trains 
}
$\endgroup$
  • 1
    $\begingroup$ Thanks for the edit. However, I want to highlight that it's important to answer the question that was asked. The question wasn't "How do I solve this problem?" or "What would be some pseudocode to solve this problem?", but rather "Why do we need to sort both the arrival and departure ties?". I don't see anything here that answers the "why" question. The answer to a "why" question needs to involve explanation of why ("because...."), rather than just an algorithm that codifies the approach already described in the question or restating that approach in English. $\endgroup$ – D.W. Jan 27 '17 at 23:30
  • $\begingroup$ @D.W. I thought the single timeline would tell the story. I added some more. If you want to delete (again) OK with me. $\endgroup$ – paparazzo Jan 27 '17 at 23:59
  • $\begingroup$ I'm still not seeing anything here that answers the question. $\endgroup$ – David Richerby Jan 29 '17 at 13:03
  • $\begingroup$ @DavidRicherby What part don't you understand? $\endgroup$ – paparazzo Jan 29 '17 at 13:19
  • $\begingroup$ @Paparazzi I didn't say that I don't understand it. I said that it doesn't answer the question. $\endgroup$ – David Richerby Jan 29 '17 at 13:33

protected by Community Jan 27 '17 at 22:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.