Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1847.html

1847. Closest Room

Level

Hard

Description

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomId_i, size_i] denotes that there is a room with room number roomId_i and size equal to size_i. Each roomId_i is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferred_j, minSize_j]. The answer to the j-th query is the room number id of a room such that:

  • The room has a size of at least minSize_j, and
  • abs(id - preferred_j) 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 j-th 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 <= 10^5
  • k == queries.length
  • 1 <= k <= 10^4
  • 1 <= roomId_i, preferred_j <= 10^7
  • 1 <= size_i, minSize_j <= 10^7

Solution

Sort rooms according to sizes in decreasing order. Sort queries according to minSizes in decreasing order, and store the queries’ indices in the original queries.

Use a tree set to store the room numbers. Loop over the sorted queries. For each query, loop over the sorted rooms and add all the rooms that have sizes greater than or equal to the current query’s minSize to the tree set. Then use preferred to find the two closest room numbers in the tree set, which are floor and ceiling. If neither floor nor ceiling exists, the query result is -1. If only one of floor and ceiling exists, the query result is the one that exists. If both floor and ceiling exist, then calculate the differences and the query result is the one with the minimum difference.

  • class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int roomsCount = rooms.length;
        int queriesCount = queries.length;
        Arrays.sort(rooms, new Comparator<int[]>() {
            public int compare(int[] room1, int[] room2) {
                return room2[1] - room1[1];
            }
        });
        int[][] newQueries = new int[queriesCount][3];
        for (int i = 0; i < queriesCount; i++) {
            newQueries[i][0] = queries[i][0];
            newQueries[i][1] = queries[i][1];
            newQueries[i][2] = i;
        }
        Arrays.sort(newQueries, new Comparator<int[]>() {
            public int compare(int[] query1, int[] query2) {
                return query2[1] - query1[1];
            }
        });
        TreeSet<Integer> set = new TreeSet<Integer>();
        int roomIndex = 0;
        int[] answer = new int[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            int[] query = newQueries[i];
            int preferred = query[0], minSize = query[1], index = query[2];
            while (roomIndex < roomsCount && rooms[roomIndex][1] >= minSize) {
                set.add(rooms[roomIndex][0]);
                roomIndex++;
            }
            Integer floor = set.floor(preferred), ceiling = set.ceiling(preferred);
            if (floor == null && ceiling == null)
                answer[index] = -1;
            else if (floor == null)
                answer[index] = ceiling;
            else if (ceiling == null)
                answer[index] = floor;
            else {
                int difference1 = preferred - floor, difference2 = ceiling - preferred;
                if (difference1 <= difference2)
                    answer[index] = floor;
                else
                    answer[index] = ceiling;
            }
        }
        return answer;
    }
}

  • // OJ: https://leetcode.com/problems/closest-room/
// Time: O(RlogR + QlogQ + QlogR)
// Space: O(R)
class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& R, vector<vector<int>>& Q) {
        sort(begin(R), end(R), [](auto &a, auto &b) { return a[1] < b[1]; });
        vector<int> ans(Q.size(), -1);
        for (int i = 0; i < Q.size(); ++i) Q[i].push_back(i);
        sort(begin(Q), end(Q), [](auto &a, auto &b) { return a[1] > b[1]; });
        set<int> ids;
        int i = R.size() - 1;
        for (auto &q : Q) {
            int pref = q[0], mn = q[1], index = q[2];
            while (i >= 0 && R[i][1] >= mn) ids.insert(R[i--][0]);
            auto it = ids.lower_bound(pref);
            int d1 = INT_MAX, d2 = INT_MAX;
            if (it != ids.end()) d2 = *it - pref;
            if (it != ids.begin()) d1 = pref - *prev(it);
            if (d1 != INT_MAX || d2 != INT_MAX) ans[index] = d1 <= d2 ? *prev(it) : *it;
        }
        return ans;
    }
};

  • # 1847. Closest Room
# https://leetcode.com/problems/closest-room

from sortedcontainers import SortedList

class Solution:
    def closestRoom(self, rooms, queries):
        Q = sorted([(y, x, i) for i, (x,y) in enumerate(queries)])[::-1]
        R = sorted((y, x) for x, y in rooms)[::-1]
        n, q = len(R), len(Q)
        p1, p2, aval, ans = 0, 0, SortedList(), [-1]*q

        while p1 <= n and p2 < q:
            if p1 < n and R[p1][0] >= Q[p2][0]:
                aval.add(R[p1][1])
                p1 += 1
            else:
                if len(aval) != 0:
                    preferred, ind = Q[p2][1], Q[p2][2]
                    i = aval.bisect(preferred)
                    
                    cands = []
                    if i > 0: cands.append(aval[i-1])
                    if i < len(aval): cands.append(aval[i])
                    ans[ind] = min(cands, key = lambda x: abs(x - preferred))

                p2 += 1

        return ans


  • func closestRoom(rooms [][]int, queries [][]int) []int {
	n, k := len(rooms), len(queries)
	sort.Slice(rooms, func(i, j int) bool { return rooms[i][1] < rooms[j][1] })
	idx := make([]int, k)
	ans := make([]int, k)
	for i := range idx {
		idx[i] = i
		ans[i] = -1
	}
	sort.Slice(idx, func(i, j int) bool { return queries[idx[i]][1] < queries[idx[j]][1] })
	rbt := redblacktree.NewWithIntComparator()
	merge := func(rbt *redblacktree.Tree, key, value int) {
		if v, ok := rbt.Get(key); ok {
			nxt := v.(int) + value
			if nxt == 0 {
				rbt.Remove(key)
			} else {
				rbt.Put(key, nxt)
			}
		} else {
			rbt.Put(key, value)
		}
	}
	for _, room := range rooms {
		merge(rbt, room[0], 1)
	}
	i := 0

	for _, j := range idx {
		prefer, minSize := queries[j][0], queries[j][1]
		for i < n && rooms[i][1] < minSize {
			merge(rbt, rooms[i][0], -1)
			i++
		}
		if i == n {
			break
		}
		c, _ := rbt.Ceiling(prefer)
		f, _ := rbt.Floor(prefer)
		if c != nil {
			ans[j] = c.Key.(int)
		}
		if f != nil && (ans[j] == -1 || ans[j]-prefer >= prefer-f.Key.(int)) {
			ans[j] = f.Key.(int)
		}
	}
	return ans
}

All Problems

All Solutions