Untitled

import java.util.*;

public class TaxiEarnings {
    public long maxTaxiEarnings(int n, int[][] rides) {
        // Sort rides by start time to make it easier to process
        Arrays.sort(rides, (a, b) -> a[0] - b[0]);

        // Use memoization to store results of subproblems
        long[] memo = new long[rides.length];
        Arrays.fill(memo, -1);

        // Start the recursion from the first ride
        return helper(rides, 0, memo);
    }

    private long helper(int[][] rides, int index, long[] memo) {
        // Base case: If no more rides are left, return 0
        if (index >= rides.length) {
            return 0;
        }

        // If the result is already computed, return it
        if (memo[index] != -1) {
            return memo[index];
        }

        // Current ride details
        int start = rides[index][0];
        int end = rides[index][1];
        int tip = rides[index][2];

        // Calculate earnings if we take the current ride
        long take = (end - start + tip) + helper(rides, findNextRide(rides, end), memo);

        // Calculate earnings if we skip the current ride
        long skip = helper(rides, index + 1, memo);

        // Store the maximum of the two options in memo
        memo[index] = Math.max(take, skip);

        return memo[index];
    }

    // Helper function to find the next ride that starts after the current ride ends
    private int findNextRide(int[][] rides, int end) {
        int left = 0;
        int right = rides.length;

        // Perform binary search to find the next ride
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (rides[mid][0] < end) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        TaxiEarnings solution = new TaxiEarnings();

        // Example 1
        int n1 = 5;
        int[][] rides1 = {{2, 5, 4}, {1, 5, 1}};
        System.out.println(solution.maxTaxiEarnings(n1, rides1)); // Output: 7

        // Example 2
        int n2 = 20;
        int[][] rides2 = {{1, 6, 1}, {3, 10, 2}, {10, 12, 3}, {11, 12, 2}, {12, 15, 2}, {13, 18, 1}};
        System.out.println(solution.maxTaxiEarnings(n2, rides2)); // Output: 20
    }
}