943. Exam Hall Seats
An exam hall has n seats in one row, numbered 0 to n-1. Build ExamHallSeats with the constructor taking n.
seat() places a student in the free seat whose distance to the closest occupied seat is as large as possible, and returns that seat number. Distance is the absolute difference of seat numbers. If the hall is empty the student takes seat 0. If several seats are equally good, choose the smallest seat number. The wall is not a neighbour: a student at an end only counts occupied seats.
leave(p) frees seat p, which is occupied. A call to seat only happens when a free seat exists. Each call must be faster than scanning all seats.
Example 1
- Input:
- operations = ["ExamHallSeats","seat","seat","seat","seat","leave","seat"]arguments = [[7],[],[],[],[],[3],[]]
- Output:
- [null,0,6,3,1,null,3]
- Explanation:
Seats 0, 6, 3 and 1 fill in that order (ties go to the smaller seat). After seat 3 empties, seats 3 and 4 are both at distance 2 from their closest neighbour, so seat 3 wins.
Example 2
- Input:
- operations = ["ExamHallSeats","seat","seat","leave","seat"]arguments = [[2],[],[],[0],[]]
- Output:
- [null,0,1,null,0]
- Explanation:
Seats 0 and 1 fill in order; after seat 0 is vacated the next student sits there again.
Constraints
1 ≤ n ≤ 109
At most 3000 calls to seat and leave in total
leave is only called on an occupied seat; seat is only called when the hall is not full
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log k) per call
- Space
- O(k)