Find the Latest Unoccupied Arrival Time That Still Boards a Bus

### Problem Buses depart at the distinct times in `buses`, each taking at most capacity waiting passengers in increasing arrival-time order. Existing distinct arrival times are in `passengers`. You may arrive no later than a bus departure but cannot share any existing passenger's arrival time. Return your latest possible arrival time that still lets you board some bus. Inputs need not be sorted. ```cpp class Solution { public: int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity); }; ``` ### Examples **Example 1:** ```text Input: buses = [5,9], passengers = [2,8,9], capacity = 2 Output: 7 Explanation: The final bus is filled by arrivals 8 and 9. Arriving at 7 boards before both; arrival 8 is forbidden because an existing passenger uses it. ``` **Example 2:** ```text Input: buses = [6], passengers = [2,4], capacity = 3 Output: 6 Explanation: The bus has one spare seat, and nobody else arrives at its departure time 6. ``` ### Constraints - `1 <= buses.length, passengers.length, capacity <= 100000`. - Every departure/arrival is between 2 and 10^9 inclusive. - Departure times are unique; passenger arrival times are unique. ### Clarifying Questions - Can you arrive at a bus departure time? Yes, if a seat is available when your turn in the queue is reached. - Can you tie an existing passenger's arrival? No, even if that passenger does not catch a bus. - Does each bus take the earliest waiting people first? Yes. - Are the arrays sorted? Not necessarily. ```hint Check the boundary Check both an occupied arrival time and a departure time with an empty seat. ```