Flight Location Query (Where is the user at time T?)

Problem: Query a User’s Airport at a Given Time (including “in-flight”) You are given a list of flight records flights. Each record contains: userId: the user identifier from: departure airport code (string) to: arrival airport code (string) departTime: departure time (an integer timestamp or any comparable integer) arriveTime: arrival time (integer), with arriveTime > departTime Given a query (userId, time), return where the user is at moment time. Location rules Consider all flights for the same userId in chronological order: In flight: if time falls strictly inside a flight interval (after departure and before arrival), return the empty string "". Waiting between flights: if time is after the previous flight arrives and before the next flight departs (exact boundary rules per spec), the user is at the previous flight’s arrival airport; return that airport code. Before the first flight departs: if time is before the first flight’s departure, the user is at the first flight’s departure airport. After the last flight arrives: if time is after the last flight’s arrival, the user is at the last flight’s arrival airport. Task Implement a function that: Input: flights and a query (userId, time) Output: a string (airport code or "") Constraints / requirements flights may include multiple users. Let n be the number of flights for the queried user. Aim for O(log n) query time (e.g., group by userId, sort by time, then binary search). You may assume flights for the same userId do not overlap in time (otherwise the location is ambiguous). Example For a user with flights: SFO -> LAX, depart=10, arrive=20 LAX -> JFK, depart=30, arrive=50 Queries: (userId, 5) -> "SFO" (userId, 15) -> "" (userId, 25) -> "LAX" (userId, 60) -> "JFK" Note: You must define and consistently apply the rule for time == departTime and time == arriveTime (whether that counts as in-flight or at an airport). Example Input 3 u1 SFO LAX 10 20 u1 LAX JFK 30 50 u2 SEA SFO 5 8 6 u1 5 u1 15 u1 25 u1 60 u2 1 u2 6 Output SFO LAX JFK SEA