1396. Design Underground System

 一刷 07/2022

Version #1 HashMap

Time O(1)

Space O(N^2 + P) - N is number of stations, P is number of passengers

Runtime: 235 ms, faster than 19.99% of Java online submissions for Design Underground System.

Memory Usage: 105 MB, less than 24.78% of Java online submissions for Design Underground System.

class UndergroundSystem {

    // key-startStation,endStation value-sum of all travel times, count of customers

    Map<List<String>, Pair<Long, Integer>> timeMap;

    // key-customer id, value-startStation,checkin time

    Map<Integer, Pair<String, Integer>> checkinMap;

    public UndergroundSystem() {

        this.timeMap = new HashMap<>();

        this.checkinMap = new HashMap<>();

    }

    

    public void checkIn(int id, String stationName, int t) {

        checkinMap.put(id, new Pair(stationName, t));

    }

    

    public void checkOut(int id, String stationName, int t) {

        if (!checkinMap.containsKey(id)) {

            return;

        }

        Pair<String, Integer> checkinInfo = checkinMap.get(id);

        List<String> stations = new ArrayList<>();

        stations.add(checkinInfo.getKey());

        stations.add(stationName);

        int duration = t - checkinInfo.getValue();

        Pair<Long, Integer> stationInfo = timeMap.getOrDefault(stations, new Pair(0l, 0));

        Pair<Long, Integer> nInfo = new Pair(stationInfo.getKey() + duration, stationInfo.getValue() + 1);

        timeMap.put(stations, nInfo);

    }

    

    public double getAverageTime(String startStation, String endStation) {

        Pair<Long, Integer> stationInfo = timeMap.get(new ArrayList<>(Arrays.asList(new String[]{startStation, endStation})));

        return (1.0 * stationInfo.getKey()) / stationInfo.getValue();

    }

}