Trains and Platforms Editorial

Practice Problem Link: Trains And Platforms | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given the arrival and departure times for n trains at a railway station. Find the minimum number of platforms the railway station needs so that none of the trains has to wait. The time is given in minutes from midnight. All trains have departures on the same day.

Naive Approach

The simple solution is to check every discrete point in the given interval and find out at which particular point the maximum number of trains will be present at the station.

• Run two nested loops, the first loop to traverse through all the points in the given range (0 to 1440) and the inner loop to traverse the arrival and departure time of each train.
• For each point, count the number of intervals that overlap that point.
• After traversing the inner loop for each point, update the answer with the maximum count of overlaps.

Analysis

• Time Complexity: O(n*max(arrival, departure))
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Train class definition
class Train {
public:
   int arrival, departure;
   Train(int arrival, int departure) {
       this->arrival = arrival;
       this->departure = departure;
   }
};
*/
int minPlatforms(vector<Train*> &trains) {
   int requiredPlatforms = 0;
   for (int i = 0; i < 1440; i++) {
       int trainsAtOnePoint = 0;
       for (int j = 0; j < trains.size(); j++) {
           if(i >= trains[j]->arrival && i <= trains[j]->departure) {
               trainsAtOnePoint++;
           }
       }
       requiredPlatforms = max(requiredPlatforms,trainsAtOnePoint);
   }
   return requiredPlatforms;
}

Java

class Solution {
   /* This is the Train class definition
   class Train {
       public int arrival, departure;
       public Train(int arrival, int departure) {
           this.arrival = arrival;
           this.departure = departure;
       }
   }
   */
   
   int minPlatforms(Train[] trains) {
       int requiredPlatforms = 0;
       for (int i = 0; i < 1440; i++) {
           int trainsAtOnePoint = 0;
           for (int j = 0; j < trains.length; j++) {
               if(i >= trains[j].arrival && i <= trains[j].departure) {
                   trainsAtOnePoint++;
               }
           }
           requiredPlatforms = Math.max(requiredPlatforms,trainsAtOnePoint);
       }
       return requiredPlatforms;
   }
}

Optimal Approach

The problem can be solved efficiently after sorting all the arrival and departure timings and keeping the count of trains currently at the station. 

• Traverse the sorted arrival and departure timings. For each arrival, the count of trains will be increased by one and for each departure count of the train will be decreased by one. 
• Keep updating the maximum count after every arrival.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Train class definition
class Train {
public:
   int arrival, departure;
   Train(int arrival, int departure) {
       this->arrival = arrival;
       this->departure = departure;
   }
};
*/
int minPlatforms(vector<Train*> &trains) {
   vector<int> sortedArrivals, sortedDepartures;
   int requiredPlatforms = 0, n = trains.size();
   for (int i = 0 ; i < n; i++) {
       sortedArrivals.push_back (trains[i]->arrival);
       sortedDepartures.push_back (trains[i]->departure);
   }
   sort(sortedArrivals.begin(), sortedArrivals.end());
   sort(sortedDepartures.begin(), sortedDepartures.end());
   int i = 0, j = 0, currentTrains = 0;
   while (i != n && j != n) {
       if (sortedArrivals[i] <= sortedDepartures[j]) {
           currentTrains++;
           i++;
           requiredPlatforms = max (requiredPlatforms, currentTrains);
       } else {
           currentTrains--;
           j++;
       }
   }
   return requiredPlatforms;
}

Java

class Solution {
   /* This is the Train class definition
   class Train {
       public int arrival, departure;
       public Train(int arrival, int departure) {
           this.arrival = arrival;
           this.departure = departure;
       }
   }
   */
   
   int minPlatforms(Train[] trains) {
       int requiredPlatforms = 0, n = trains.length;
       int[] sortedArrivals = new int[n];
       int[] sortedDepartures = new int[n];
       for (int i = 0 ; i < n; i++) {
           sortedArrivals[i] = trains[i].arrival;
           sortedDepartures[i] = trains[i].departure;
       }
       Arrays.sort(sortedArrivals);
       Arrays.sort(sortedDepartures);
       int i = 0, j = 0, currentTrains = 0;
       while (i != n && j != n) {
           if (sortedArrivals[i] <= sortedDepartures[j]) {
               currentTrains++;
               i++;
               requiredPlatforms = Math.max (requiredPlatforms, currentTrains);
           } else {
               currentTrains--;
               j++;
           }
       }
       return requiredPlatforms;
   }
}