Latest Arrival to Catch a Bus
Updated
Problem statement
You are given bus departure times buses, existing passenger arrival times passengers, and the seat count capacity of each bus.
Buses depart in order of time. At each departure, up to capacity waiting passengers board in increasing arrival-time order. A passenger arriving exactly at departure may board. Passengers left behind wait for a later bus.
You want to join the queue. Choose a nonnegative integer arrival time different from every existing passenger arrival time. Return the latest time that lets you board any bus.
Times within each input array are distinct. The input arrays may be unsorted, and passengers may be empty. Your arrival joins the same boarding order. Do not change either input array.
Function
latestArrival(buses: int[], passengers: int[], capacity: int) → intExamples
Example 1
buses = [10,20]passengers = [2,17,18,19]capacity = 2return = 16The first bus takes arrival 2. The last bus fills with arrivals 17 and 18. Arriving at 16 gets a seat; 17, 18, and 19 are occupied times, while arriving at 20 leaves you behind.
Example 2
buses = [5,10]passengers = [1,2]capacity = 2return = 10The first bus takes both existing passengers. The last bus has free seats, so arrival 10 is allowed.
Example 3
buses = [2]passengers = [1,2]capacity = 1return = 0The bus has one seat. Arrival 1 is forbidden and arrival 2 is too late to get ahead of arrival 1. Arrival 0 gets the seat.
Constraints
- 1 <= buses.length <= 10^5
- 0 <= passengers.length <= 10^5
- 1 <= buses[i] <= 10^9
- 1 <= passengers[i] <= 10^9
- 1 <= capacity <= 10^5
- Bus departure times are distinct, and passenger arrival times are distinct.
More Autodesk interview questions
Similar questions at other companies
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- Find Minimum Possible SizeMathWorks · OAMathWorks interview questions
- Minimum Days to Watch All MoviesAdobe · OAAdobe interview questions
- Efficient Janitor TripsRoblox · OARoblox interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Can Every Package Fit in a BoxIMC Trading · OAIMC Trading interview questions
- Minimum Tunnel Crossing TimeArcesium · OAArcesium interview questions
- Get Maximum PairsAmazon · OA