Java: DP O(n+m)
Firstly, note we can sort rides by the starting point to use in DP and achieve O(n+mlogm) time complexity:\n\nstatic int START= 0, END= 1, TIP= 2;\npublic long 
Firstly, note we can sort rides by the starting point to use in DP and achieve O(n+mlogm) time complexity:\n```\nstatic int START= 0, END= 1, TIP= 2;\npublic long maxTaxiEarnings(int n, int[][] rides) {\n\tint m= rides.length;\n\tArrays.sort(rides, (r1, r2)->r1[START]-r2[START]);\n\tlong[] dp= new long[n+1];        \n\tfor(int i=1, j=0; i<=n; i++){\n\t\tdp[i]= Math.max(dp[i-1], dp[i]);\n\t\t// consider all rides starting at i i.e. rides[j][0]==i \n\t\tfor(; j<m; j++){\n\t\t\tint start= rides[j][START], end= rides[j][END], tip= rides[j][TIP];\n\t\t\tif(start!=i) break;\n\t\t\tdp[end]= Math.max(dp[end], dp[start]+end-start+tip);\n\t\t}\n\t}\n\treturn dp[n];\n}\n```\nThe order of processing rides matters only as far as the starting point though - so instead of full O(mlogm) sort, we can bucket rides by their starting point to achieve the overall **O(n+m)** time complexity:\n```\nstatic int START= 0, END= 1, TIP= 2;  \npublic long maxTaxiEarnings(int n, int[][] rides) {\n\t// bucket rides by pick up point in O(m)\n\tArrayList<int[]>[] rideBuckets= new ArrayList[n+1];\n\tfor(int[] ride:rides){\n\t\tArrayList<int[]> bucket= rideBuckets[ride[START]];\n\t\tif(bucket==null) bucket= rideBuckets[ride[START]]= new ArrayList<>();\n\t\tbucket.add(ride);\n\t}\n\t// consider all rides starting at i i.e. ride[START]==i  in O(n+m)\n\tlong[] dp= new long[n+1];\n\tfor(int i=1; i<=n; i++){\n\t\tdp[i]= Math.max(dp[i-1], dp[i]);\n\t\tif(rideBuckets[i]!=null)\n\t\tfor(int[] ride:rideBuckets[i]){\n\t\t\tint start= ride[START], end= ride[END], tip= ride[TIP];\n\t\t\tdp[end]= Math.max(dp[end], dp[start]+end-start+tip);\n\t\t}\n\t}\n\treturn dp[n];\n}\n```
[]