Maximum Earnings From Taxi - Practice Coding Problems

Maximum Earnings From Taxi - Problem

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [start_i, end_i, tip_i] denotes the ith passenger requesting a ride from point start_i to point end_i who is willing to give a tip_i dollar tip.

For each passenger i you pick up, you earn end_i - start_i + tip_i dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Input & Output

Example 1 — Basic Multiple Rides

$ Input: n = 5, rides = [[2,5,4],[1,5,1]]

› Output: 7

💡 Note: Pick up the passenger from point 2 to point 5 with tip 4. Earnings = 5-2+4 = 7. The other ride overlaps so we can't take both.

Example 2 — Non-overlapping Rides

$ Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]

› Output: 20

💡 Note: Take rides [1,6,1], [10,12,3], and [12,15,2] for earnings 6+5+5=16, or find better combination [3,10,2] + [12,15,2] + [13,18,1] = 9+5+6=20

Example 3 — Single Ride

$ Input: n = 3, rides = [[1,3,0]]

› Output: 2

💡 Note: Only one ride available from point 1 to 3 with no tip. Earnings = 3-1+0 = 2

Constraints

1 ≤ n ≤ 10⁵
1 ≤ rides.length ≤ 3 × 10⁴
rides[i].length == 3
1 ≤ start_i < end_i ≤ n
1 ≤ tip_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

We have rides with start, end points and tips. Need to pick non-overlapping rides.

Sort & Apply DP

Sort by end time and use DP to make optimal choices at each step.

Maximum Earnings

The final DP value gives us the maximum possible earnings.

Key Takeaway

🎯 Key Insight: Sort rides by end time and use DP to choose between taking each ride (plus best non-overlapping previous) or skipping it

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is to use dynamic programming after sorting rides by end time. For each ride, we choose between taking it (plus best earnings from non-overlapping previous rides) or skipping it. The optimal approach uses bottom-up DP with binary search to achieve O(n log n) time complexity and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Generate all possible combinations of non-overlapping rides and find maximum earnings
Bottom-Up Dynamic Programming	O(n log n)	O(n)	Sort rides by end time and use iterative DP with binary search
Memoization - Top Down DP	O(n² log n)	O(n²)	Use recursion with memoization to avoid recalculating subproblems

Brute Force - Try All Combinations — Algorithm Steps

For each ride, decide to take it or skip it
If taking a ride, ensure no overlap with previous rides
Calculate earnings for each valid combination
Return the maximum earnings found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Combinations

Try every possible subset of non-overlapping rides

Calculate Earnings

For each valid combination, sum up the earnings

Find Maximum

Return the combination with highest earnings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int start, end, tip;
} Ride;

int compare(const void* a, const void* b) {
    Ride* rideA = (Ride*)a;
    Ride* rideB = (Ride*)b;
    return rideA->start - rideB->start;
}

long long backtrack(Ride* rides, int ridesCount, int index, int lastEnd) {
    if (index >= ridesCount) {
        return 0;
    }
    
    // Skip current ride
    long long skip = backtrack(rides, ridesCount, index + 1, lastEnd);
    
    // Take current ride if possible
    long long take = 0;
    if (rides[index].start >= lastEnd) {
        long long earnings = rides[index].end - rides[index].start + rides[index].tip;
        take = earnings + backtrack(rides, ridesCount, index + 1, rides[index].end);
    }
    
    return (skip > take) ? skip : take;
}

long long solution(int n, Ride* rides, int ridesCount) {
    qsort(rides, ridesCount, sizeof(Ride), compare);
    return backtrack(rides, ridesCount, 0, 0);
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse rides array
    Ride rides[1000];
    int ridesCount = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            sscanf(ptr, "[%d,%d,%d]", &rides[ridesCount].start, &rides[ridesCount].end, &rides[ridesCount].tip);
            ridesCount++;
        }
        ptr++;
    }
    
    long long result = solution(n, rides, ridesCount);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

For each of n rides, we have 2 choices (take or skip), leading to 2^n combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth can go up to n levels

⚡ Linearithmic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler