1002. Closest Suitable Room
A hostel has n rooms, listed as rooms[i] = [id, size]; room numbers may repeat, which simply means two rooms with the same number. Each guest request is [preferred, minSize].
For every request return the room number of a room whose size is at least minSize and whose number is closest to preferred (smallest |id - preferred|). When two room numbers are equally close, return the smaller one. If no room is big enough, return -1. Requests are independent: nothing is booked.
Return one number per request, in order. Aim for roughly O((n + q) log n) time and O(n + q) space.
Example 1
- Input:
- rooms = [[14,30],[6,12],[22,45],[9,60],[31,20]]queries = [[10,25],[25,50],[0,70],[8,10]]
- Output:
- [9,9,-1,9]
- Explanation:
Query (10,25): rooms 14 (30), 22 (45) and 9 (60) are big enough, and 9 is nearest to 10 (distance 1). Query (25,50) accepts only room 9, so 9; (0,70) accepts none; (8,10) picks 9 (distance 1) over 6 (distance 2).
Example 2
- Input:
- rooms = [[40,5],[50,5],[60,9]]queries = [[45,5],[55,9],[70,6]]
- Output:
- [40,60,60]
- Explanation:
Query (45,5): rooms 40 and 50 are both 5 away, so the smaller id 40 wins; (55,9) needs size 9, only room 60 qualifies; (70,6) accepts only room 60.
Constraints
1 ≤ n = rooms.length ≤ 105
0 ≤ q = queries.length ≤ 2000
1 ≤ id, size ≤ 106; 0 ≤ preferred, minSize ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n + q)