Have you noticed that there is always a train ready to go at the time of a trip departure? there is no delay, that have to be planned someway, this is exactly what we were asked to do, we were to do a program to calculate the minimal number of trains required to accomplish all the trips on time.

Click here to download the problem statement.

Step 1: Analyzing the problem

The main I used to solve this is that we can't have more trains than trips from each station, I mean, if you have 3 trips that start in station A then you need at least three trains from A unless some of they just came from station B, the same occur for B, using this I started a counter for each station and started it with the number of trips that begins in that station.

If we find any trip that can be taken by a train that arrives from the another station, we reduce the counter by one. After processing all lists, the counter will tell us how many trips weren't taken by a trains from the another station which is the number of trains we need.

The question is, how do we know if a a train that comes from the another station will be able to take the new trip?.

First we need to calculate the "availability time" for each trip, given the arrival time, and the turnaround time, we easily calculate the availability time as follows:

availability time = arrival time + turnaround time

Now its simple, we just compare the availability time of a train after a trip with the departure time of the trips in the new station.

Something important is to order the list of trips before comparing, but this must be done carefully, yeah, because when you go from A to B, list on A have to be ordered by "availability time", and the list on B have to be ordered by "departure time", that way you just have to find the first trip you can take with a recently arrived train. The same apply when analyzing the lists from B to A so we have to reorder the lists by the corresponding properties.

Step 2: Start coding

First we will store the information for each trip in a new class, I've called it Train, but a better name could be Trip, anyway this contains the information we need, availability time, departure time, and the next Train(or Trip) assigned.

public class Train
{
	var availabilityTime:int;
	var departureTime:int;
	var nextTrain:Train;
	public function Train(){}
}

As we said in the Step 1, we need two ordered list, to order the Train lists by availability and departure criteria, we need to implement the following functions.

// Let us order a Train list by Availbility
public function orderByAvailability(t1:Train, t2:Train):Number{
	if(t1.availabilityTime > t2.availabilityTime) return 1;
	return (t1.availabilityTime < t2.availabilityTime)? -1: 0; 
}
// Let us order a Train list by Departure
public function orderByDeparture(t1:Train, t2:Train):Number{
	if(t1.departureTime > t2.departureTime) return 1;
	return (t1.departureTime < t2.departureTime)? -1: 0; 
}

Finally, we need to implement the core logic function.

// This functions implements the logic of your solution
private function TransformInput(inputData:Array):Array{
	var outputData:Array = []; // Output lines
	// Read the number of cases
	var N:int = parseInt(inputData[0][0]);
	var index:int = 1;
	for(var caseNumber:int = 1; caseNumber <= N; caseNumber++){
		var trainListA:Array = [];
		var trainListB:Array = [];
		var turnaroundTime:int = parseInt(inputData[index][0]);
		index++;
		// Read the number of trips from A and B
		var NA:int = parseInt(inputData[index][0]);
		var NB:int = parseInt(inputData[index][1]);
		index++;
		// Start the counters
		var trainsFromA:int = NA; 
		var trainsFromB:int = NB;
		
		// We calculate the availability and departure times in minutes
		// and add each trip to the lists
		var availabilityTime:int;
		var departureTime:int;
		var arrTmp:Array;
		// Trips from A
		for(var i:int = index; i < index + NA; i++){
			arrTmp = (inputData[i][0] as String).split(":");
			departureTime = parseInt(arrTmp[0]) * 60 + parseInt(arrTmp[1]);
			arrTmp = (inputData[i][1] as String).split(":");
			availabilityTime = parseInt(arrTmp[0]) * 60 + parseInt(arrTmp[1]) + turnaroundTime;
			var t1:Train = new Train();
			t1.departureTime = departureTime;
			t1.availabilityTime = availabilityTime;
			trainListA.push(t1);
		}
		index += NA;
		// Trips from B
		for(i = index; i < index + NB; i++){
			arrTmp = (inputData[i][0] as String).split(":");
			departureTime = parseInt(arrTmp[0]) * 60 + parseInt(arrTmp[1]);
			arrTmp = (inputData[i][1] as String).split(":");
			availabilityTime = parseInt(arrTmp[0]) * 60 + parseInt(arrTmp[1]) + turnaroundTime;
			var t2:Train = new Train();
			t2.departureTime = departureTime;
			t2.availabilityTime = availabilityTime;
			trainListB.push(t2);
		}
		index += NB;
		
		// Sort each list to evaluate trips from A to B
		trainListA.sort(orderByAvailability);
		trainListB.sort(orderByDeparture);
		// The followinf variables let us know that trains are assigned to another in the oposite station
		var assignedA:Array = [];
		var assignedB:Array = [];
		
		for(i = 0; i < trainListA.length; i++){
			for(var j:int = 0; j < trainListB.length; j++){
				if((trainListA[i] as Train).availabilityTime <= (trainListB[j] as Train).departureTime){
					// Validating if the train is assigned already
					if(assignedB.indexOf(trainListB[j]) < 0){
						assignedB.push(trainListB[j]);
						(trainListA[i] as Train).nextTrain = trainListB[j];
						trainsFromB--;
						break;
					}
				}
			}
		}
		// Sort each list to evaluate trips from B to A
		trainListB.sort(orderByAvailability);
		trainListA.sort(orderByDeparture);
		for(i = 0; i < trainListB.length; i++){
			for(j = 0; j < trainListA.length; j++){
				if((trainListB[i] as Train).availabilityTime <= (trainListA[j] as Train).departureTime){
					// Validating if the train is assigned already
					if( assignedA.indexOf(trainListA[j]) < 0 && assignedA.indexOf((trainListB[i] as Train).nextTrain) < 0){
						assignedA.push(trainListA[j]);
						(trainListB[i] as Train).nextTrain = trainListA[j];
						trainsFromA--;
						break;
					}
				}
			}
		}
		outputData.push(StringUtil.substitute("Case #{0}: {1} {2}", caseNumber, trainsFromA, trainsFromB));
	} 

	return outputData;
}

Working solution