Given a bench with n seats and few people sitting, tell the seat number each time when a new person goes to sit on the bench such that his distance from others is maximum?
G jia
A few clarifying questions that i would ask:
1. What if the bench is emtpy. Can i return any seat number?
2. What if bench is full. Should i return -1.
3. How big can n be?
4. How many queries are we making?
Algo:
1. Traverse the bench once (saved as array or vector) and populate a max heap based on distance between two occupied seats. For each node in heap have distance, start seat no and end seat no.
2. When a query is made return the seat no as (end seat no - start seat no)/2 for the root node in heap.
3. Replace the root node with one node formed by (end seat no - start seat no)/2 and end seat no and call heapIfY() on heap.
4. insert the seconds node formed by start node no and (end seat no - start seat no)/2 in the heap.
Repeat process from 2 to 4 for each query.
Complexity:
Forming heap: O(n)
For each query: O(log(n))