Necessary and Sufficient

Apart from the Save The Universe puzzle the qualification round also had a train timetable problem. Here you are given a train timetable for multiple overlapping trips between 2 stations and you need to work out the quantity of rolling-stock needed at both stations to satisfy it.

All that is needed to solve this puzzle is to pair up the inbound arrivals and the outgoing departures at each station, allowing for the turnaround time. That is, you start with no trains and add only as they are needed to satisfy the timetable when existing trains can't. (If you are having trouble understanding that draw yourself a train graph.)

It is effectively another greedy algorithm like that used in Save The Universe but I'll omit the formal proof as it should be intuitively obvious that it produces the optimal solution.

After initial data loading and sorting, the running time of the algorithm is going to be O(n), however since sorting the data has complexity of O(n log n) on average (worst case is O(n²)) then it must follow that the overall runtime of the proposed algo is also O(n log n).

The C# code is shown below:

using System;
using System.Collections.Generic;
using System.IO;

namespace GoogleCodeJam.TrainTimetable
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader infile = new System.IO.StreamReader("large.txt");
            StreamWriter outfile = new System.IO.StreamWriter("output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++)
            {
                int turnaroundTime = Int32.Parse(infile.ReadLine());    // in minutes

                string[] tripCounts = (infile.ReadLine()).Split(new char[] {' '}, StringSplitOptions.None);
                int tripsFromA = Int32.Parse(tripCounts[0]);
                int tripsFromB = Int32.Parse(tripCounts[1]);

                List<DateTime> DeparturesFromA = new List<DateTime>();
                List<DateTime> ArrivalsAtA = new List<DateTime>();
                List<DateTime> DeparturesFromB = new List<DateTime>();
                List<DateTime> ArrivalsAtB = new List<DateTime>();

                for (int i = 0; i < tripsFromA; i++)
                {
                    string[] times = (infile.ReadLine()).Split(new char[] {' '}, StringSplitOptions.None);
                    DateTime depart = DateTime.Parse(times[0]);
                    DateTime arrive = DateTime.Parse(times[1]).AddMinutes(turnaroundTime);
                    DeparturesFromA.Add(depart);
                    ArrivalsAtB.Add(arrive);
                }

                for (int i = 0; i < tripsFromB; i++)
                {
                    string[] times = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                    DateTime depart = DateTime.Parse(times[0]);
                    DateTime arrive = DateTime.Parse(times[1]).AddMinutes(turnaroundTime);
                    DeparturesFromB.Add(depart);
                    ArrivalsAtA.Add(arrive);
                }

                // need to sort the items so we can process them chronologically
                DeparturesFromA.Sort();
                ArrivalsAtA.Sort();
                DeparturesFromB.Sort();
                ArrivalsAtB.Sort();

                int trainCountA = 0;
                int trainCountB = 0;

                while (DeparturesFromA.Count>0)
                {
                    if ((ArrivalsAtA.Count == 0) || (ArrivalsAtA[0] > DeparturesFromA[0]))
                    {
                        // we DON'T have an inbound train that will suffice
                        trainCountA++;
                    }
                    else
                    {
                        // we've got this one covered
                        ArrivalsAtA.RemoveAt(0);
                    }
                    DeparturesFromA.RemoveAt(0);
                }

                while (DeparturesFromB.Count > 0)
                {
                    if ((ArrivalsAtB.Count == 0) || (ArrivalsAtB[0] > DeparturesFromB[0]))
                    {
                        // we DON'T have an inbound train that will suffice
                        trainCountB++;
                    }
                    else
                    {
                        // we've got this one covered
                        ArrivalsAtB.RemoveAt(0);
                    }
                    DeparturesFromB.RemoveAt(0);
                }

                outfile.WriteLine(String.Format("Case #{0}: {1} {2}", caseNo, trainCountA, trainCountB));
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}