[Java] HashMap DP, no sorting
dp[i] stores the intermediate result for index i.\n\n\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] rides) {\n        long[] dp = new long[n
dp[i] stores the intermediate result for index i.\n\n```\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] rides) {\n        long[] dp = new long[n + 1];\n        \n        Map<Integer, List<int[]>> map = new HashMap<>();\n        \n        for(int[] ride : rides){\n            List<int[]> entry = map.getOrDefault(ride[1], new ArrayList<>());\n            entry.add(ride);\n            map.put(ride[1], entry);\n        }\n        \n        \n        for(int i = 1; i <= n; i++){\n\t\t\t// scenario 1: no rides taken. same as i - 1.\n            dp[i] = dp[i - 1];\n            \n\t\t\t// scenario 2: take a ride which ends at i\n            if(map.containsKey(i)){\n                for(int[] ride : map.get(i)){\n                    dp[i] = Math.max(dp[i], dp[ride[0]] + ride[1] - ride[0] + ride[2]);\n                }\n            }\n        }\n        \n        return dp[n];\n    }\n}\n\n```
[]