[Java] DP + Binary Search Solution with comments, TC: O(mlogm)
\n\npublic long maxTaxiEarnings(int n, int[][] rides) {\n        //Time complexity: mlogm\n        Arrays.sort(rides, (a, b) -> (a[1] - b[1]));//sort rides by t
\n```\npublic long maxTaxiEarnings(int n, int[][] rides) {\n        //Time complexity: mlogm\n        Arrays.sort(rides, (a, b) -> (a[1] - b[1]));//sort rides by their end time\n        int m = rides.length;\n        long[] dp = new long[m + 1];// dp[i]: the maximum dollars you can earn given rides [1, i];\n        for (int i = 1; i <= m; i++) {\n            int curProfit = rides[i - 1][1] - rides[i - 1][0] + rides[i - 1][2];\n            int idx = bs(rides, 0, i - 1, rides[i - 1][0]);//find the largest index that its rides[idx][1] is smaller than or equal to target\n            if (idx == -1) {//no non-overlapping rides before this ride\n                dp[i] = Math.max(dp[i - 1], curProfit);\n            } else {//either take the current passager or leave it\n                dp[i] = Math.max(dp[i - 1], dp[idx + 1] + curProfit);\n            }\n        }\n        return dp[m];\n    }\n    private int bs(int[][] arr, int l, int r, int target) {\n        while (l <= r) {\n            int mid = l + (r - l) / 2;\n            if (arr[mid][1] <= target) {\n                l = mid + 1; \n            } else {\n                r = mid - 1;\n            }\n        }\n        return r;\n    }\n```
[]