LeetCode 2008: Maximum Earnings From Taxi Solution
Master LeetCode problem 2008 (Maximum Earnings From Taxi), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2008. Maximum Earnings From Taxi
Problem Explanation
Explanation
To solve this problem, we can use dynamic programming. We start by sorting the rides array based on the end points. Then, we iterate through each ride and calculate the maximum earnings we can achieve up to that ride. For each ride, we have two choices: either to pick up the passenger or not. If we pick up the passenger, we add the earnings from that ride to the maximum earnings we had up to the starting point of the ride. If we don't pick up the passenger, we simply update the maximum earnings using the previous ride.
After iterating through all rides, the maximum earnings will be the maximum value in our earnings array. We return that value as the result.
Time Complexity: O(nlogn) where n is the number of rides
Space Complexity: O(n)
Solution Code
class Solution {
public long maxTaxiEarnings(int n, int[][] rides) {
Arrays.sort(rides, (a, b) -> a[1] - b[1]);
long[] earnings = new long[n + 1];
int rideIndex = 0;
for (int i = 1; i <= n; i++) {
earnings[i] = earnings[i - 1];
while (rideIndex < rides.length && rides[rideIndex][1] == i) {
int start = rides[rideIndex][0];
int end = rides[rideIndex][1];
int tip = rides[rideIndex][2];
earnings[i] = Math.max(earnings[i], earnings[start] + end - start + tip);
rideIndex++;
}
}
return earnings[n];
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2008 (Maximum Earnings From Taxi)?
This page provides optimized solutions for LeetCode problem 2008 (Maximum Earnings From Taxi) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2008 (Maximum Earnings From Taxi)?
The time complexity for LeetCode 2008 (Maximum Earnings From Taxi) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2008 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2008 in Java, C++, or Python.