Trains scheduled, find max platforms per stations

Question

Given a "folder" which contains many "files," each file contains a time-table of trains, which stations they halt on and what time, per day.

File-1 for day-1
Train1    [station1, <1  - 3> ] [station2, <5  - 6> ] 
Train2    [station1, <10 - 12>] [station3, <15 - 18>] 

File-2 for day-2
Train1    [station1,  <11  - 4> ] [station2, <5  - 6> ] 
Train2    [station1, <8 -   2>] [station3, <15 - 18>]

Overlapping days are included in the same file.

E.g: If trains halt from 23.00 - 00.30 then this data would be present in one of the files only.

We ignore timezones and use 00 - 23.59 scale instead of am and pm.

To find how many platforms a station would need given such daily schedules.

E.g: If Train1 and Train2 both use Station1 from 10 - 12 then Station1 needs two platforms.

Complexity:

\$O\$ ( file * stations * (intervals * log intervals) )

• file - each file in the folder, aka number of days, whose schedule has been given : constituted by - for (File file : folder.listFiles()) {

• stations - constituted by dailyStationPlatformCountMap()

• intervals - sort inside maxOverlappingInterval

Note: I do understand merits of unit testing in separate files. But I deliberately added it to the main method for personal convenience, so I request that you don't consider that in your feedback.

I'm looking for request code review, optimizations and best practices.

final class Intervals implements Serializable {
    private final int start;
    private final int end;

    public Intervals (int start, int end) {
        this.start = start;
        this.end = end;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }
}

public final class TrainTimeTable {

    private TrainTimeTable() { }

    public static Map<String, Integer> stationMaxPlatformMap(String folderName) throws IOException, ClassNotFoundException {
        File folder = new File(folderName);
        final List<Map<String, Integer>> stationPlatformCountList = new ArrayList<Map<String,Integer>>();
        for (File file : folder.listFiles()) {
            if (file.toString().contains("DS_Store")) continue;
            ObjectInputStream ois = new ObjectInputStream(new FileInputStream(file));
            final Map<String, Map<String, Intervals>> dailyTrainStationIntervalMap = (Map<String, Map<String, Intervals>>) ois.readObject();
            final Map<String, List<Intervals>> dailyStationIntervalMap = getDailyPerStationIntervalMap(dailyTrainStationIntervalMap);
            final Map<String, Integer> dailyStationPlatformCountMap = dailyStationPlatformCountMap(dailyStationIntervalMap);
            stationPlatformCountList.add(dailyStationPlatformCountMap);
        }
        return yearlyMaxPlatforms(stationPlatformCountList);
    }

    /**
     * Breaks down the the information 'per train' into information 'per station'
     * From here on the 'trains' don't hold any relevance, as we have created the time-table per station.
     * ie - all intervals with respect to a station are mapped to the station.
     * 
     * @param trainStationIntervalMap   :  map of trains -> to stations and train's intervals on those stations
     * @return                          :  map of station -> to all intervals of all trains on that station.
     */
    private static Map<String, List<Intervals>> getDailyPerStationIntervalMap(Map<String, Map<String, Intervals>> trainStationIntervalMap) {
        final Map<String, List<Intervals>> dailyStationInterval = new HashMap<String, List<Intervals>>();
        for (Map<String, Intervals>  map  : trainStationIntervalMap.values()) {
            for (Entry<String, Intervals> entry : map.entrySet()) {
                final String station = entry.getKey();
                final Intervals interval = entry.getValue();

                if (!dailyStationInterval.containsKey(station)) {
                    dailyStationInterval.put(station, new ArrayList<Intervals>());
                }
                dailyStationInterval.get(station).add(interval);
            }
        }
        return dailyStationInterval;
    }


    /**
     * Given a map of station -> all intervals belonging to the station, return the maximum platforms that may be needed.
     * 
     * @param dailyStationIntervalMap   : map of station -> all intervals of that station.
     * @return
     */
    private static Map<String, Integer> dailyStationPlatformCountMap(Map<String, List<Intervals>> dailyStationIntervalMap) {
        final Map<String, Integer> dailyStationMaxPlatformCount = new HashMap<String, Integer>();
        for (Entry<String, List<Intervals>> entry : dailyStationIntervalMap.entrySet()) { 
            String station = entry.getKey();
            List<Intervals> intervalList = entry.getValue();
            dailyStationMaxPlatformCount.put(station,  maxOverlappingInterval(intervalList));
        }
        return dailyStationMaxPlatformCount;
    }

    /**
     * Given a station and its intervals, find the max platforms needed.
     * Station is a 'meeting room'
     * interval is understandably 'interval'
     * platforms simply corresponds to 'overlap'
     * 
     * http://stackoverflow.com/questions/8969823/how-to-find-the-maximal-number-of-these-intervals-that-have-a-common-point
     * 
     * @param startTime
     * @param endTime
     * @return
     */
    private static int maxOverlappingInterval (List<Intervals> interval) {
        int[] startTime = new int[interval.size()];
        int[] endTime = new int[interval.size()];

        populateAndSort(startTime, endTime, interval);

        int i = 0;  // ctr for start time array
        int j = 0;  // ctr for end time array
        int count  = 0;
        int max = -1;

        while (i < startTime.length) {
            if (startTime[i]  < endTime[j]) {
                count++;
                i++;
                if (count > max) {
                    max = count;
                }
            } else if (startTime[i] > endTime[j]) {
                count--;
                j++;
            } else {
                i++;
                j++;
            }
        }
        return max;
    }

    private static void populateAndSort(int[] startTime, int[] endTime, List<Intervals> interval) {
        for (int i = 0; i < interval.size(); i++) {
            startTime[i] = interval.get(i).getStart();
            endTime[i] = interval.get(i).getEnd();
        }
        Arrays.sort(startTime);
        Arrays.sort(endTime);
    }

    /**
     * Once a list of 365 maps of Stations -> max plaform needed per day, we need to find, 
     * wbat was the max platform needed by Station for entire year.
     * Example:
     * If station "foo" needed 6 plaforms on Jan 16, and 4 plaforms on July 8th, then 6 should be added to map.
     * ie 
     * foo -> 6
     * bar -> 8 etc.
     * 
     * @param stationPlatformCountList  : list of daily station to max platform count per day map.
     * @return
     */
    private static Map<String, Integer> yearlyMaxPlatforms(List<Map<String, Integer>> stationPlatformCountList) {
        final Map<String, Integer> yearlyStationPlatformCountMap = new HashMap<String, Integer>();
        for (int i = 0; i < stationPlatformCountList.size(); i++) {
            for (Entry<String, Integer> entry : stationPlatformCountList.get(i).entrySet()) {
                String station = entry.getKey();
                int platformCount = entry.getValue();
                if (!yearlyStationPlatformCountMap.containsKey(station) || yearlyStationPlatformCountMap.get(station) < platformCount) {
                    yearlyStationPlatformCountMap.put(station, platformCount);
                }
            } 
        }
        return yearlyStationPlatformCountMap;
    }

    public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException {
        // create a directory:
        new File("/Users/ameya.patil/Desktop/schedules").mkdir(); 

        Map<String, Map<String, Intervals>> map1 = new HashMap<String, Map<String,Intervals>>();

        Map<String, Intervals> stationInterval11 = new HashMap<String, Intervals>();
        stationInterval11.put("Churchgate", new Intervals(1, 2));
        stationInterval11.put("Dadar", new Intervals(4, 6));
        stationInterval11.put("Bandra", new Intervals(8, 10));
        map1.put("T1", stationInterval11);

        Map<String, Intervals> stationInterval12 = new HashMap<String, Intervals>();
        stationInterval12.put("Churchgate", new Intervals(1, 3));
        stationInterval12.put("Dadar", new Intervals(6, 9));
        stationInterval12.put("Bandra", new Intervals(12, 15));
        map1.put("T2", stationInterval12);

        Map<String, Intervals> stationInterval13 = new HashMap<String, Intervals>();
        stationInterval13.put("Churchgate", new Intervals(1, 4));
        stationInterval13.put("Dadar",      new Intervals(5, 9));
        stationInterval13.put("Bandra",     new Intervals(13, 17));
        map1.put("T3", stationInterval13);

        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/Users/ameya.patil/Desktop/schedules/dayOne"))) {
            oos.writeObject(map1);
        }

        Map<String, Map<String, Intervals>> map2 = new HashMap<String, Map<String,Intervals>>();

        Map<String, Intervals> stationInterval21 = new HashMap<String, Intervals>();
        stationInterval21.put("Churchgate", new Intervals(1, 2));
        stationInterval21.put("Dadar", new Intervals(4, 6));
        stationInterval21.put("Bandra", new Intervals(8, 10));
        map2.put("T1", stationInterval21);

        Map<String, Intervals> stationInterval22 = new HashMap<String, Intervals>();
        stationInterval22.put("Churchgate", new Intervals(1, 3));
        stationInterval22.put("Dadar", new Intervals(6, 9)); 
        stationInterval22.put("Bandra", new Intervals(9, 15));
        map2.put("T2", stationInterval22);

        Map<String, Intervals> stationInterval23 = new HashMap<String, Intervals>();
        stationInterval23.put("Churchgate", new Intervals(12, 14));
        stationInterval23.put("Dadar",      new Intervals(5, 9));
        stationInterval23.put("Bandra",     new Intervals(13, 17));
        map2.put("T3", stationInterval23);

        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/Users/ameya.patil/Desktop/schedules/dayTwo"))) {
            oos.writeObject(map2);
        }

        /**
         * Expected stuff:
         * Dadar  : 2
         * Churchgate  : 3
         * Bandra  : 2
         */
        final Map<String, Integer> expected = new HashMap<String, Integer>();
        expected.put("Dadar", 2);
        expected.put("Churchgate", 3);
        expected.put("Bandra", 2);


        assertEquals(expected, stationMaxPlatformMap("/Users/ameya.patil/Desktop/schedules"));
    }
}

Answer 1

Quick review, but still good coding like usual.

Naming :

int i = 0;  // ctr for start time array
int j = 0;  // ctr for end time array

Isn't it better to call them pointerStartTime and pointerEndTime?
It helps you when you are programming. Take in mind that you get this code and must find a little bug.
You are getting a headache just by always thinking what i and j are

Check for your own faults :

private static void populateAndSort(int[] startTime, int[] endTime, List<Intervals> interval) {
    for (int i = 0; i < interval.size(); i++) {
        startTime[i] = interval.get(i).getStart();
        endTime[i] = interval.get(i).getEnd();
    }
    Arrays.sort(startTime);
    Arrays.sort(endTime);
}

Its a strange set up and you can make a mistake when you call this method, by not setting the length of the array big enough.
At least this you should be doing :

private static void populateAndSort(int[] startTime, int[] endTime, List<Intervals> interval) {
    if ((startTime.length != endTime.length) || (startTime.length != interval.size())) {
        throw new IllegalArgumentException("All sizes must be the same");
    }
    for (int i = 0; i < interval.size(); i++) {
        startTime[i] = interval.get(i).getStart();
        endTime[i] = interval.get(i).getEnd();
    }
    Arrays.sort(startTime);
    Arrays.sort(endTime);
}

To avoid "abuse" of the method you should do the creation of the int[] in your method self :

private static Map<String,int[]> getTimesFromIntervals (List<Intervals> intervals>) {

In the javaDoc you tell exactly that the key for startTime[] is starttime and so on.
This is then clear for every programmer that will use that method.
You see that I cut the sorting to from that method.
I prefer a new method for sorting the 2 arrays :

private static void sortIntegerMap (Map<String,int[]> timesMap) {
    for (int[] time : timesMap.values()) {
        Arrays.sort(time);
    }
}

Now you have a more generic method that can sort, even more entries in the map is no problem.

Hope you have something from this review.