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, where abs(x) is the absolute value of x.

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: Greedy

• Time complexity: O(nlogn+klogk+klogn)
• Space complexity: O(n+k)

 

JavaScript

/**
 * @param {number[][]} rooms
 * @param {number[][]} queries
 * @return {number[]}
 */
const closestRoom = function (rooms, queries) {
  const n = rooms.length;
  const k = queries.length;
  const indexdQueries = queries.map(([preferred, minSize], index) => {
    return { preferred, minSize, index };
  });
  const result = Array.from({ length: k }, () => -1);
  const sortedRooms = [];
  let roomIndex = 0;

  const insertRoom = id => {
    let left = 0;
    let right = sortedRooms.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      if (sortedRooms[mid] < id) left = mid + 1;
      else right = mid;
    }

    sortedRooms.splice(left, 0, id);
  };

  const searchClosest = id => {
    if (!sortedRooms.length) return -1;
    let left = 0,
      right = sortedRooms.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (sortedRooms[mid] < id) left = mid + 1;
      else right = mid - 1;
    }

    if (left >= sortedRooms.length && right < 0) return -1;
    if (right < 0) return sortedRooms[left];
    if (left >= sortedRooms.length) return sortedRooms[right];
    const leftDiff = Math.abs(sortedRooms[left] - id);
    const rightDiff = Math.abs(sortedRooms[right] - id);

    if (leftDiff === rightDiff) return Math.min(sortedRooms[left], sortedRooms[right]);

    return leftDiff > rightDiff ? sortedRooms[right] : sortedRooms[left];
  };

  rooms.sort((a, b) => b[1] - a[1]);
  indexdQueries.sort((a, b) => b.minSize - a.minSize);

  for (const { preferred, minSize, index } of indexdQueries) {
    while (roomIndex < n && rooms[roomIndex][1] >= minSize) {
      const roomId = rooms[roomIndex][0];

      insertRoom(roomId);
      roomIndex += 1;
    }

    result[index] = searchClosest(preferred);
  }

  return result;
};