Chess Club Drop-In Guide
Indices of shortest intervals covering query times, ties by lowest index
A chess club publishes a list of supervised study sessions. A visitor may drop into any session that is running at their arrival time, but prefers the session with the shortest total scheduled duration.
Each entry sessions[i] = [start, end] describes a session running over the half-open interval [start, end): it includes start but does not include end. Its duration is end - start. Times are integer offsets from the club's reference clock, so negative times are allowed.
For each time in arrivals, select the running session with the smallest duration. If several running sessions have the same duration, select the one with the smallest original index in sessions.
Return a list of selected zero-based session indices, in the original order of arrivals. Use -1 for an arrival when no session is running. Each arrival is considered independently; selecting a session does not change its availability.
Examples
Example 1
Input: sessions = [[0,9],[2,5],[5,7]], arrivals = [3,5,9] Output: [1,2,-1]
At time 3, sessions 0 and 1 are running, and session 1 is shorter. At time 5, session 1 has ended and session 2 has started; session 2 is shorter than session 0. Time 9 is excluded from every session.
Example 2
Input: sessions = [[-3,4],[-3,4],[0,1]], arrivals = [-3,0,1,0,4] Output: [0,2,0,2,-1]
The first two sessions have identical durations and boundaries, so their overlap is resolved by original index. At time 0, the third session is preferred because it is shorter. At time 1, that short session has ended. Repeated arrival times are evaluated independently.
Constraints
- 0 <= sessions.length <= 1800
- 0 <= arrivals.length <= 1800
- Each sessions[i] contains exactly two integers start and end with start < end.
- -10^9 <= start, end, arrivals[j] <= 10^9
- Sessions and arrival times need not be sorted, and duplicates are allowed.
The intended complexity is O(n log n + q log q + (n + q) log(n + 1)) time and O(n + q) space, where n is the number of sessions and q is the number of arrivals. No bookings are consumed by a query.
Hints
Show hint 1Hint 1
Process arrival times in sorted order while remembering where each answer belongs.
Show hint 2Hint 2
Keep sessions that have already started in a heap ordered by duration and original index. An ended session only needs to be removed when it reaches the top.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the boundary checks change if sessions included both their start and end times?
- How would you answer online arrivals, where their order cannot be changed, if the entire session list were still known in advance?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem