## Problem A taxi driver has a single vehicle and a list of trip requests. Each trip has a start time, end time, and fare. The driver can complete only one trip at a time (trips cannot overlap). Find the maximum total fare the driver can earn. ```python def max_taxi_earnings(trips: list[tuple[int, int, int]]) -> int: """trips: [(start, end, fare), ...]. Return max total fare.""" pass ``` ``` Input: trips = [(0,5,10), (3,7,15), (5,10,20), (6,9,8)] Output: 30 # Take (0,5,10) then (5,10,20) -> total 30 # OR take (3,7,15) -> only 15 # 30 is optimal Input: trips = [(1,4,3), (2,5,6), (4,6,2)] Output: 5 # Take (1,4,3) then (4,6,2) -> total 5 # OR (2,5,6) alone -> 6 is better! Output: 6 ``` ## Follow-ups 1. This is the weighted interval scheduling problem — what DP approach solves it optimally? 2. After sorting by end time, how do you efficiently find the latest non-overlapping trip using binary search? 3. What is the time complexity of your solution? 4. Extend to `k` taxis — how does the problem change?

InterviewDB Question

Taxi Driver: Maximize Earnings by Scheduling Passenger Trips

phone

Question Details

Problem A taxi driver has a single vehicle and a list of trip requests. Each trip has a start time, end time, and fare. The driver can complete only one trip at a time (trips cannot overlap). Find the maximum total fare the driver can earn. Follow-ups This is the weighted interval scheduling problem — what DP approach solves it optimally? After sorting by end time, how do you efficiently find the latest non-overlapping trip using binary search? What is the time complexity of your solution? Exten…

Full Details

🔒

Unlock all Ziphq questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a ziphq interview during the phone round.

It covers the following topics: Dynamic Programming, Binary Search, Phone, Coding, Onsite .

Topics

Dynamic Programming Binary Search Phone Coding Onsite

Taxi Driver: Maximize Earnings by Scheduling Passenger Trips

Question Details

Full Details

About This Question

Topics

More Ziphq Interview Questions