The Latest Time to Catch a Bus — LeetCode 2332 Python Solution

The problem

You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth passenger.

Example

Input

buses = [10,20], passengers = [2,17,18,19], capacity = 2

Output

16

Explanation

Suppose you arrive at time 16.

Python solution

class Solution:
    def latestTimeCatchTheBus(
        self, buses: List[int], passengers: List[int], capacity: int
    ) -> int:
        buses.sort()
        passengers.sort()
        j = 0
        for t in buses:
            c = capacity
            while c and j < len(passengers) and passengers[j] <= t:
                c, j = c - 1, j + 1
        j -= 1
        ans = buses[-1] if c else passengers[j]
        while ~j and passengers[j] == ans:
            ans, j = ans - 1, j - 1
        return ans

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2332. The Latest Time to Catch a Bus is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems