Closest Room

// Accepted solution for LeetCode #1847: Closest Room
class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int n = rooms.length;
        int k = queries.length;
        Arrays.sort(rooms, (a, b) -> a[1] - b[1]);
        Integer[] idx = new Integer[k];
        for (int i = 0; i < k; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) -> queries[i][1] - queries[j][1]);
        int i = 0;
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int[] room : rooms) {
            tm.merge(room[0], 1, Integer::sum);
        }
        int[] ans = new int[k];
        Arrays.fill(ans, -1);
        for (int j : idx) {
            int prefer = queries[j][0], minSize = queries[j][1];
            while (i < n && rooms[i][1] < minSize) {
                if (tm.merge(rooms[i][0], -1, Integer::sum) == 0) {
                    tm.remove(rooms[i][0]);
                }
                ++i;
            }
            if (i == n) {
                break;
            }
            Integer p = tm.ceilingKey(prefer);
            if (p != null) {
                ans[j] = p;
            }
            p = tm.floorKey(prefer);
            if (p != null && (ans[j] == -1 || ans[j] - prefer >= prefer - p)) {
                ans[j] = p;
            }
        }
        return ans;
    }
}

// Accepted solution for LeetCode #1847: Closest Room
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
}

# Accepted solution for LeetCode #1847: Closest Room
class Solution:
    def closestRoom(
        self, rooms: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        rooms.sort(key=lambda x: x[1])
        k = len(queries)
        idx = sorted(range(k), key=lambda i: queries[i][1])
        ans = [-1] * k
        i, n = 0, len(rooms)
        sl = SortedList(x[0] for x in rooms)
        for j in idx:
            prefer, minSize = queries[j]
            while i < n and rooms[i][1] < minSize:
                sl.remove(rooms[i][0])
                i += 1
            if i == n:
                break
            p = sl.bisect_left(prefer)
            if p < len(sl):
                ans[j] = sl[p]
            if p and (ans[j] == -1 or ans[j] - prefer >= prefer - sl[p - 1]):
                ans[j] = sl[p - 1]
        return ans

// Accepted solution for LeetCode #1847: Closest Room
/**
 * [1847] Closest Room
 *
 * 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 j^th 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 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 <= roomIdi, preferredj <= 10^7
 * 	1 <= sizei, minSizej <= 10^7
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/closest-room/
// discuss: https://leetcode.com/problems/closest-room/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn closest_room(rooms: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        vec![]
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1847_example_1() {
        let rooms = vec![vec![2, 2], vec![1, 2], vec![3, 2]];
        let queries = vec![vec![3, 1], vec![3, 3], vec![5, 2]];

        let result = vec![3, -1, 3];

        assert_eq!(Solution::closest_room(rooms, queries), result);
    }

    #[test]
    #[ignore]
    fn test_1847_example_2() {
        let rooms = vec![vec![1, 4], vec![2, 3], vec![3, 5], vec![4, 1], vec![5, 2]];
        let queries = vec![vec![2, 3], vec![2, 4], vec![2, 5]];

        let result = vec![2, 1, 3];

        assert_eq!(Solution::closest_room(rooms, queries), result);
    }
}

// Accepted solution for LeetCode #1847: Closest Room
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1847: Closest Room
// class Solution {
//     public int[] closestRoom(int[][] rooms, int[][] queries) {
//         int n = rooms.length;
//         int k = queries.length;
//         Arrays.sort(rooms, (a, b) -> a[1] - b[1]);
//         Integer[] idx = new Integer[k];
//         for (int i = 0; i < k; i++) {
//             idx[i] = i;
//         }
//         Arrays.sort(idx, (i, j) -> queries[i][1] - queries[j][1]);
//         int i = 0;
//         TreeMap<Integer, Integer> tm = new TreeMap<>();
//         for (int[] room : rooms) {
//             tm.merge(room[0], 1, Integer::sum);
//         }
//         int[] ans = new int[k];
//         Arrays.fill(ans, -1);
//         for (int j : idx) {
//             int prefer = queries[j][0], minSize = queries[j][1];
//             while (i < n && rooms[i][1] < minSize) {
//                 if (tm.merge(rooms[i][0], -1, Integer::sum) == 0) {
//                     tm.remove(rooms[i][0]);
//                 }
//                 ++i;
//             }
//             if (i == n) {
//                 break;
//             }
//             Integer p = tm.ceilingKey(prefer);
//             if (p != null) {
//                 ans[j] = p;
//             }
//             p = tm.floorKey(prefer);
//             if (p != null && (ans[j] == -1 || ans[j] - prefer >= prefer - p)) {
//                 ans[j] = p;
//             }
//         }
//         return ans;
//     }
// }