1847. Closest Room
Description
There is a hotel with n
rooms. The rooms are represented by a 2D integer array rooms
where rooms[i] = [roomIdi, sizei]
denotes that there is a room with room number roomIdi
and size equal to sizei
. Each roomIdi
is guaranteed to be unique.
You are also given k
queries in a 2D array queries
where queries[j] = [preferredj, minSizej]
. The answer to the jth
query is the room number id
of a room such that:
- The room has a size of at least
minSizej
, and abs(id - preferredj)
is minimized, whereabs(x)
is the absolute value ofx
.
If there is a tie in the absolute difference, then use the room with the smallest such id
. If there is no such room, the answer is -1
.
Return an array answer
of length k
where answer[j]
contains the answer to the jth
query.
Example 1:
Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]] Output: [3,-1,3] Explanation: The answers to the queries are as follows: Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3. Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1. Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.
Example 2:
Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]] Output: [2,1,3] Explanation: The answers to the queries are as follows: Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2. Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller. Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.
Constraints:
n == rooms.length
1 <= n <= 105
k == queries.length
1 <= k <= 104
1 <= roomIdi, preferredj <= 107
1 <= sizei, minSizej <= 107
Solutions
Solution 1: Offline Query + Ordered Set + Binary Search
We notice that the order of queries does not affect the answer, and the problem involves the size relationship of room areas. Therefore, we can sort the queries in ascending order of minimum area, so that we can process each query from small to large. Also, we sort the rooms in ascending order of area.
Next, we create an ordered list and add all room numbers to the ordered list.
Then, we process each query from small to large. For each query, we first remove all rooms with an area less than or equal to the current query's minimum area from the ordered list. Then, in the remaining rooms, we use binary search to find the room number closest to the current query. If there is no such room, we return $-1$.
The time complexity is $O(n \times \log n + k \times \log k)$, and the space complexity is $O(n + k)$. Where $n$ and $k$ are the number of rooms and queries, respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|